[Tutor] Binary chop function - this works, but I'm not sure why

[Arun Srinivasan]

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!