Infinite loop in binary search

Question

I am trying to implement 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 when run, gets into a infinite loop. How can I correct that?

Answer 1

Since, you are not updating the value of mid the while loop keeps on checking the same element and runs into an infinite loop, to correct that as many people have pointed out, update mid in the while loop.
Also, you should do low = mid+1 and not low = mid.

The full code is given 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!