二进制搜索中的无限循环

Question

我正在尝试使用以下函数实现二进制搜索:

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

运行时的上述函数进入无限循环.我怎么能纠正这个？

Answer 1

因为，您没有更新midwhile 循环的值，但会继续检查相同的元素并陷入无限循环，为了纠正这一点，正如许多人指出的那样，请mid在 while 循环中更新。
另外，你应该做low = mid+1和不应该做low = mid。

完整代码如下：-

    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

确保输入已排序！