二分查找 Python 为什么要使用 mid + 1 或 mid - 1？

Question

我正在学习二分查找，样例代码中使用了 "low = mid + 1 and high = mid - 1"，但我不明白为什么我们不能使用 "low = mid and high = mid"？

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)

- Mila

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        

- Reblochon Masque

---

你好，能否请给我一个示例？ - Mila

你好，你的解释帮助我很好地理解了Python会丢弃已经检查过的一半部分，包括边界。然而，我不明白它如何帮助搜索，因为Python将检查中间值，而不是边界。你能否请解释一下这个问题呢？ - Mila

通过检查中间值，每次搜索都会将搜索空间减半。如果每次在两端减少1个搜索范围，您将更快地收敛于找到所需值的过程中。 - Reblochon Masque

Answer 2

请允许我尝试解释二分查找的原理。假设我们有以下序列 A=[-5, 10, 14, 33, 42, 42, 42]，并且要查找的值为 searched_value = 14，那么我们可以得到：

Iteration 1,     lo = 0, hi = 6, mid = 3     A[mid] > 14
Iteration 2,     lo = 0, hi = 2, mid = 1     A[mid] < 14
Iteration 3,     lo = 2, hi = 2, mid = 2     A[mid] = 14  (found!)

在算法的每次迭代中，我们可以得出结论，lo和hi始终包含搜索值的位置，并且我们将通过对迭代次数进行归纳来证明它：

归纳假设：如果搜索值存在于序列中，则它始终包含在lo和hi之间。

基本情况：在第一次迭代中，lo=0和hi=n-1包含所有元素，因此，如果搜索值存在于序列中，则它将包含在lo和hi之间，不变式显然是正确的。

归纳步骤：在任何一步中，如果搜索值包含在lo和hi之间，则它将在下一次迭代中继续包含在lo和hi之间。我们有3种可能性（这里是问题的答案）：

• 如果 A[mid] = searched_value：在这种情况下，算法正确地报告了序列中搜索值的位置，并且不变量是正确的，因为搜索值位于lo和hi之间。
• 如果 A[mid] < searched_value：知道它是一个排序序列，所有A[lo...mid] < searched_value（包括A[mid]）之间的元素，因此我们可以将lo=mid+1（安全地只搜索上半部分），并且不变量仍然在下一次迭代中保持正确。
• 如果 A[mid] > searched_value：知道它是一个排序序列，所有A[mid...hi] > searched value（包括A[mid]）之间的元素，因此我们可以将hi=mid-1（安全地只搜索下半部分），并且不变量仍然在下一次迭代中保持正确。

考虑到在每次迭代中，算法总是在较小的序列段上进行搜索，因此终止条件是保证的，因为要么只有一个元素与 searched_value 相同，要么在下一次迭代中，算法将报告该元素不在序列中。

因此，该算法被证明是正确的（这也是我们使用 mid+1 和 mid-1 的原因）。

- Wilfredo

Answer 3

我认为代码不起作用，因为当数组大小为偶数时，在 while 循环中你不会退出，当我们让 l 或 r 等于 mid（错误），而不是 mid +1 或 mid-1（正确）。

如下所示，它陷入了无尽的循环。

例如：

Binary Search
Array = [8, 9,   11, 13]; target = 10
         0  1    2   3 
         l  m        r   m = (0 + 3)/2 = 1.5 or 1, arr[m] < target (coz 9 < 10), make l = m, 
            l    m   r   m = (1+3)/2 = 2, arr[m] > target (coz 11 > 10), make r = m, 
            l(m) r       m = (1+2)/2 = 1.5 or 1, arr[m] < target (coz 9 < 10), make l = m
            l    r(m)    m = (1+3)/2 = 2, arr[m] > target (coz 11 > 10), make r = m.
            l(m) r       m = (1+2)/2 = 1.5 or 1, arr[m] < target (coz 9 < 10), make l = m
            l    r(m)    m = (1+3)/2 = 2, arr[m] > target (coz 11 > 10), make r = m.
            ...
            ...

- Coderworld1017