algorithm - 如何从逻辑上解释二进制搜索的任何变体

Question

似乎有八种二分搜索的变体(给定一个按升序排列的排序列表):

1. 小于目标的最大数(但最左边的重复项)

2. 小于目标的最大数(但最右边的重复数)

3. 小于或等于目标的最大数(但最左边的重复数)

4. 小于或等于目标的最大数(但重复项的最右边)

5. 大于目标的最小数字(但最左边的重复项)

6. 大于目标的最小数字(但最右边的重复项)

7. 大于或等于目标的最小数字(但最左边的重复项)

8. 大于或等于目标的最小数字(但最右边的重复项)

我怎么知道如何正确和逻辑地为这些设置正确类型的二进制搜索？每次我尝试时，当列表变得非常小或出现奇怪的边缘情况时，逻辑似乎往往会失败，这让我觉得我的逻辑不正确。

有没有更好的方法从逻辑上思考这类问题，从而更好地设置二分查找？

您总是听说有很大比例的程序员无法正确编写二进制搜索代码，但后来我发现没有关于如何正确设置这 8 种情况的详尽文献，我一点也不感到惊讶。

Answer 1

我用于二分查找的心智模型如下:假设我们有一个单调递增的函数 f: [a, b] -> {0,1} 我们想从 [a, b] 中找到最小的数字 i b] 且 f(i) = 1，或者如果不存在这样的数字则为 b。以下算法将计算该结果:

lo = a, hi = b
while lo < hi:
    # invariant: lo <= i <= hi
    mid = (lo + hi)/2  # or lo + (hi - lo) / 2 to avoid overflows
    if f(mid): 
        hi = mid
    else: 
        lo = mid + 1

最后，lo = hi = i。

有趣的是，此代码永远不会检查 f(b)，因此如果 f 仅在 [a,b-1] 上定义就可以了。如果 f(b-1) = 0，则代码将报告 b 作为答案。您可以通过使用正确的函数 f 来涵盖您提到的所有情况。例如:

(7) Smallest number greater than or equal to target (but leftmost of duplicates)

假设您有一个大小为 n 的数组。

使用 a = 0, b = n, f(i) = array[i] >= target

(1) Largest number less than target (but rightmost of duplicates)

使用 a = -1, b = n - 1, f(i) = (array[i+1] >= target).

或者，使用 (7) 的解决方案并减去 1。应该清楚的是，我们只是将这里的所有内容都移动了 1。

(2) Largest number less than target (but leftmost of duplicates)

如果我没记错的话，这需要两次搜索。您可以使用案例 (1) 的解决方案(比如索引 i)，然后使用 a = 0, b = i, f(j) = array[j] == array[i] 找到最左边的重复项。

等等

自从我开始使用这种模式以来，我认为我从未在二分搜索中犯过错误。