python - 二进制搜索 : weird middle point calculation

Question

关于列表中点的计算:为什么会有

i = (first +last) //2 

和last被初始化为len(a_list) - 1？从我的快速测试来看，这个算法没有 -1 可以正常工作。

def binary_search(a_list, item):
    """Performs iterative binary search to find the position of an integer in a given, sorted, list.
    a_list -- sorted list of integers
    item -- integer you are searching for the position of
    """

    first = 0
    last = len(a_list) - 1

    while first <= last:
        i = (first + last) / 2

        if a_list[i] == item:
            return '{item} found at position {i}'.format(item=item, i=i)
        elif a_list[i] > item:
            last = i - 1
        elif a_list[i] < item:
            first = i + 1
        else:
            return '{item} not found in the list'.format(item=item)

Answer 1

最后一个合法索引是 len(a_list) - 1。该算法将 正常工作，因为first 将始终不超过此值，因此截断均值永远不会超出范围。但是，如果没有 -1，大约一半的时间中点计算将比最佳值大 1，导致速度略有下降。