我正在尝试使用以下函数实现二进制搜索:
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
上面的函数运行时,进入死循环。我该如何纠正?
最佳答案
因为,您没有更新 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
确保输入已排序!
关于python - 二进制搜索中的无限循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21449278/