发现在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在任何项目返回正确的索引位置。这是为什么？我已经到处去寻找这个具体问题的解释并不能找到一个。我所发现的是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

在这种情况下，你只是回报的项目。你的算法搜索一个方式从最后一个元素到一个第一线性项。

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

0 6 6
0 5 5
0 4 4
0 3 3
0 2 2
0 1 1
0 0 0