python - 二分查找 Python 为什么我们使用 mid + 1 或 mid - 1

Question

我正在学习二分搜索，示例代码使用“low = mid +1 and high = mid -1”，但我不明白为什么我们不使用“low =中和高=中 ”而不是？

def binarysearch(sequence, value):
    lo, hi = 0, len(sequence) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sequence[mid] < value:
            lo = mid + 1
        elif value < sequence[mid]:
            hi = mid - 1
        else:
            return mid
    return None

my_list = [1, 3, 5, 7, 9]
binarysearch(my_list, 3)

Answer 1

原因是为了避免重叠搜索；它将搜索范围的边界放置在尚未检查的项目上。

例如:如果 mid 位于索引 10，则左侧的下一个搜索将查找索引 9 之前的值，右侧的搜索将从索引 11 处的值开始。

                    mid
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
|                 |    |                           |
<-from 0 to mid-1->    <-- from mid+1 to the end --> 

note that in this example, the boundary values are included