binary search in python weird behavior

Question

Please look at this code:

def chop(array, search):
        lo = 0
        high = len(array) - 1
        while lo <= high:
                mid = (high + lo) /2
                if array[mid] == search:
                        return 'true'
                elif search > array[mid]:
                        low = mid + 1
                else:
                        high = mid - 1
        return 'false'



if __name__ == '__main__':
        a = [1,2,3,4,5,6,7,8,9,10]
        print chop(a, 3)

I wrote this little script which is supposed to search for number in array - regular binary search. So I run the script, and for example when I put in chop(a, 1) I get true, when I put in chop(a, 2) I get true, but when I put chop(a, 3) I don't get an answer, just empty line in the Python Shell.

Does anyone have an idea on what is going on?

Answer 1

I'm guessing this is your bug:

low = mid + 1

Your while loop uses the variable lo, and you're defining a new variable called low within your while loop. In essence, you're never updating your lo variable.

Change that line to:

lo = mid + 1

and your algorithm should work.