在 Python 中的二进制搜索算法中查找数组的中间索引值

Question

我是 Python 的新手，正在实施二分查找算法。这是算法：

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

    while low <= high:
        mid = (low + high)
        guess = list[mid]

        if guess == item:
            return mid      
        if guess > item:
            high = mid - 1      
        else:
            low = mid + 1   
    return None

我的问题是关于 mid = (low + high) 行的。无论我使用 mid = (low + high) 还是 mid = (low + high)/2，算法 returns 都是数组中任何项目的正确索引位置。这是为什么？我到处搜索这个特定问题的解释，但找不到。我所发现的是 Python 3 自动舍入不能整除的数字，所以对于元素数量为奇数的数组，比如 13，中间元素的索引将是 6。但是如何上面的算法每次都没有除以2就得到中间索引元素？

Answer 1

因为你的算法不是二分查找。

mid = (low + high)

因为高从 len(arr) - 1 开始，低总是从 0 开始，中总是从 len(arr) - 1 开始。

if guess > item:
    high = mid - 1

在这种情况下，在下一次重新计算 mid 时，mid 的值会减一。因此，如果猜测太高，它会降低一个元素。事情是因为 mid 总是从 len(arr) - 1 开始，这将永远是 True。 guess 总是从最大的元素开始，然后一个一个地下降。直到你点击：

if guess == item:
    return mid

在这种情况下，您只需 return 该项目。您的算法以一个一个的方式从最后一个元素到第一个元素线性搜索项目。

如果你真的添加了一个 print(low, high, mid) 你会得到这样的输出：

在 Python 中的二进制搜索算法中查找数组的中间索引值

Finding the middle index value of an array in a binary search algorithm in Python

binary-search

python-3.x