Binary search in python's weird behavior

Question

Take a 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 that should look for a number in an array - regular binary search. So I run the script, and for example, when I put in chop(a, 1) , I become true, when I put in chop(a, 2) , I become true, but when I put chop(a, 3) , I get no response, just empty in Python shell.

Does anyone have an idea on what's going on?

Answer 1

I assume this is your mistake:

 low = mid + 1 

The while variable uses the lo variable, and you define a new variable called low inside the while loop. Essentially, you never update the lo variable.

Change this line to:

 lo = mid + 1 

and your algorithm should work.