为什么二进制搜索算法不起作用？

Question

我从“grokking algorithms”一书中复制了代码，用于使用二进制搜索算法在列表中查找项目。代码运行良好，returns 没有错误。但是，有时它对某些数字不起作用，例如，如果我调用它来查找“1”。怎么了？

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high)/2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid + 1
        else:
            low = mid + 1
    return None

list1 = []

for i in range (1, 101):
    list1.append(i)

print(list1)
print(binary_search(list1, 1))

Answer 1

两个问题：

使用整数除法（所以在Python 3 中有效）：mid = (low + high)//2
当guess > item你想排除下一个范围的猜测值，但high = mid + 1它仍然是在范围内。更正为 high = mid - 1

为什么二进制搜索算法不起作用？

Why does binary search algorithm not work?

python

sorting

algorithm

binary-search