[Tutor] Binary chop function - this works, but I'm not sure why
Arun Srinivasan
soulguidedtelescope at gmail.com
Thu Feb 14 21:36:18 CET 2008
On Thu, Feb 14, 2008 at 11:41 AM, Arun Srinivasan
<soulguidedtelescope at gmail.com> wrote:
>
> On Thu, Feb 14, 2008 at 5:27 AM, bob gailer <bgailer at alum.rpi.edu> wrote:
> >
> > Arun Srinivasan wrote:
> > > I'm trying to learn Python, and I decided to try kata 2 </> from the
> > > CodeKate website. It's basically just a challenge to implement a
> > > binary search in different ways.
> > >
> > > I wrote an implementation that works, but I'm confused as to why.
> > >
> > > def chop(search_int, sorted_list):
> > > if len(sorted_list) == 1 or 2:
> > Yet another way to express that is:
> >
> > if 1 <= len(sorted_list) <= 2:
> >
> > > for x in sorted_list:
> > > if x == search_int:
> > > return sorted_list.index(x)
> > > return -1
> > >
> > > midpoint = (len(sorted_list) - 1) / 2
> > > mp_value = sorted_list[midpoint]
> > >
> > > if mp_value == search_int:
> > > return midpoint
> > > elif mp_value > search_int:
> > > return chop(search_int, sorted_list[:midpoint])
> > > else:
> > > return chop(search_int, sorted_list[midpoint + 1:])
> > >
> > > Basically, it only returns the index if it matches in the if statement
> > > at the beginning of the function, but since that is limited to lists
> > > of length 2 or 1, why doesn't it return only 0 or 1 as the index? I
> > > think there is something about recursion here that I'm not fully
> > > comprehending.
> > >
> > >
> > >
> > > ------------------------------------------------------------------------
> > >
> > > _______________________________________________
> > > Tutor maillist - Tutor at python.org
> > > http://mail.python.org/mailman/listinfo/tutor
> > >
> >
> >
> > --
> > Bob Gailer
> > 919-636-4239 Chapel Hill, NC
> >
> >
>
> Oy, I should have seen that. Thanks for the responses - time to go
> back and fix this.
>
Turns out it was simple to fix - just needed to fix that test so it
wasn't silly, add the lower bound tracking (thanks Alan), and make
sure to test for empty lists. Here's the function in all (rather, what
little there is) of its glory:
def chop(search_int, sorted_list, lbound = 0):
if len(sorted_list) == 0:
return -1
if len(sorted_list) in [1,2]:
if sorted_list[0] == search_int: return lbound
elif len(sorted_list) == 2 and sorted_list[1] == search_int:
return lbound + 1
else: return -1
midpoint = (len(sorted_list) - 1) / 2
mp_value = sorted_list[midpoint]
if mp_value == search_int:
return midpoint
elif mp_value > search_int:
return chop(search_int, sorted_list[:midpoint])
else:
return chop(search_int, sorted_list[midpoint + 1:], lbound +
midpoint + 1)
Alan, could you please explain why
if sorted_list[0] == search_int: return 0
elif len(sorted_list) == 2 and sorted_list[1] == search_int: return 1
else: return -1
is faster than:
> for x in sorted_list:
> if x == search_int:
> return sorted_list.index(x)
> return -1
Thanks for the help!
More information about the Tutor
mailing list