Binary Search Infinite Loop

Question

I am trying to implement a binary search with the following function:

def buggy_binary_search(input, key): low = 0 high = len(input)-1 mid = (low + high)/2 while low <= high: if input[mid] == key: return mid if input[mid] > key: high = mid - 1 else: low = mid return -1 

The above function at startup gets into an infinite loop. How can i fix this?

Answer 1

Since you are not updating the mid value, the while loop continues to test the same element and runs into an infinite loop to fix this, as many people have pointed out, update the mid in the while loop.
In addition, you should do low = mid+1 , not low = mid .

The full code is below: -

  def binary_search(input, key): low = 0 high = len(input)-1 mid = (low + high)/2 while low <= high: mid = (low + high)/2 if input[mid] == key: return mid if input[mid] > key: high = mid - 1 else: low = mid + 1 return -1 

Make sure the input is sorted!

Answer 2

 def binary_search(input, key): low = 0 high = len(input)-1 mid = (low + high)/2 while low <= high: mid = (low + high)/2 if input[mid] == key: return mid if input[mid] > key: high = mid - 1 else: low = mid + 1 return -1 

as Dmitry Bychenko said, you should put mid = (low + high) / 2 in the loop.

Answer 3

 """don't use "input" as a variable name. its a python keyword. make sure your array is sorted use integer division when computing midpoint """ def bsearch(input_array,target): lo,hi=0,len(input_array)-1 while lo<=hi: mid=(lo+hi)//2 if input_array[mid]==target: print "found at ",mid return mid if input_array[mid]>target: print "look left" hi=mid-1 if input_array[mid]<target: print "look right" lo=mid+1 return -1 a=[2,4,7,8,12,88,99,101] target=7 assert bsearch(a,1134)==-1,"value 1134 isn't in array but says it is" assert bsearch(a,2)==0,"value 2 is in the zero element of array.begenning" assert bsearch(a,101)==7,"value 101 is in the 7th element of array. end" assert bsearch(a,12)==4,"value 12 is in the 4th element of array. midpoint"