二进制搜索Python为什么我们使用中+ 1或中-1 [英] Binary search Python Why do we use mid + 1 or mid - 1

问题描述

我正在学习二进制搜索，并且示例代码使用" low = mid +1和high = mid -1 "，但我不明白为什么我们不使用" low =中高=中"?

I am learning binary search and the sample code uses" low = mid +1 and high = mid -1" but I don't understand why we do not use "low = mid and high = mid " instead?

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)

推荐答案

原因是要避免重复搜索；它将搜索范围的边界放在尚未检查的项目上.

The reason is to avoid overlapping searches; it places the boundary of the search ranges on the items that have not been checked yet.

例如:如果中点位于索引10，则下一个搜索将查找直到索引9的值，而从索引11的值开始向右搜索.

For instance: if mid is at index 10, the next search left will look at values up to index 9, and the right search from values at index 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        

这篇关于二进制搜索Python为什么我们使用中+ 1或中-1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！