[Tutor] Binary chop function - this works, but I'm not sure why
Arun Srinivasan
soulguidedtelescope at gmail.com
Thu Feb 14 20:41:16 CET 2008
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.
More information about the Tutor
mailing list