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

Question

似乎有八种二分搜索的变体（给定一个升序排序的列表）：

小于目标的最大数（但重复的最左边）
小于目标的最大数（但重复的最右边）
小于或等于目标的最大数（但最左边的重复项）
小于或等于目标的最大数字（但最右边的重复项）
大于目标的最小数字（但最左边的重复项）
大于目标的最小数字（但最右边的重复项）
大于或等于目标的最小数字（但最左边的重复项）
大于或等于目标的最小数字（但最右边的重复项）

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

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

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

Answer 1

我用于二分查找的心智模型如下：假设我们有一个单调递增的函数 f: [a, b] -> {0,1} 我们想从 [ a, 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)，因此如果仅在 [a,b-1] 上定义 f 就可以了。如果 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] 找到最左边的重复项。

等等

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

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

How to logically interpret any variation of binary search

algorithm

binary-search