python - 二进制搜索中的无限循环

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

因为，您没有更新 mid 的值，while 循环不断检查相同的元素并进入无限循环，要纠正许多人指出的问题，请更新 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

确保输入已排序!