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?

• huon: 'true' and 'false'? What about True and False?
• Nolen Royalty: Your binary search is stalling when mid = 1. Try printing the value of mid within your loop.
• John La Rooy: There is a similar function in the bisect module

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.

• bobek: That's it. I can't believe I didn't notice it! Thanks
• K Mehta: Happens to the best of us :) No worries
• nawfal: Ah, this is why I dont like python's declarations. Easy to miss.