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

[Alan Gauld]

"Arun Srinivasan" <soulguidedtelescope at gmail.com> wrote

> 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:

|This is not doing what you think it is.

Pythopn sees this as:

if ( len(sorted_list == 1) or 2:

So it evaluates whether the list is one element, if it isn't
it then checks if 2 is true, which it always is. So the if
condition is always trie and yuou code always executes
the if block. Now the if block as written will always find
the element in the list if it exists.

If you rewrote the if test like so you would get a more
effective test:

if len(sorted_list) in [1,2]:

>        for x in sorted_list:
>            if x == search_int:
>                return sorted_list.index(x)
>        return -1

You could also rewrite the block as:

if sorted_list[0] == search_int: return 0
elif len(sorted_list) == 2 and  sorted_list[1] == search_int: return 1
else return -1

Which should be marginally faster and only works for lists of
length 1 or 2.

>    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.

The rest of the code is broken because, as you say, it only returns 0 
or 1.
you need to add the lower bound to the return value but you don't 
track
the lower bound!

Alan G.