algorithm - 对缺失元素的二进制搜索是否总是返回该元素之前的位置(如果它存在)？

Question

这类似于C++中的lower_bound，二进制搜索的Javadoc也提到了这一点:“搜索键的索引，如果它包含在数组中；否则，(-(插入点) - 1)."

我已经能够通过几个示例验证它的真实性，并且我非常确定它是真实的。但是，我无法证明这一点，所以我不确定。

我试图通过反证法进行某种证明。它沿着这条线运行:如果该元素在那里，那么我们一定是通过消除包含该元素的范围而错过了它。潜在位置和它应该是的位置之间的差距必须是最小的。最后，如果有两个元素并且您检查第一个元素，即该元素，或者该元素可能所在位置后面的元素。

我也曾尝试考虑将存在元素的情况减少到没有元素的情况，但这种方法无济于事。我觉得我正在挥舞证明并捕获救命稻草。

问题中的陈述是否正确？如果是，你能证明吗？

Answer 1

这取决于您如何实现二分查找。

例如，像您描述的那样实现它的一种方法是让它搜索大于或等于您的元素的第一个元素。然后，当二分搜索停止时，它停止的位置就是答案(实际元素或应插入的位置)。

示例代码:

binary_search(v: value to search, a: list to search in, n: list size):
    left = 0, right = n

    while left < right:
        m = (left + right) / 2
        if a[m] >= v: // this is the important part:
                      // even if we find it, we continue,
                      // so we find the first such value.
            right = m
        else:
            left = m + 1

    return left

示例输出:

binary_search(3, {1, 2, 4}, 3) = 2
binary_search(0, {1, 2, 3}, 3) = 0
binary_search(2, {1, 2, 3}, 3) = 1

这对于适应您提到的格式的返回值应该是微不足道的。

执行here ，我们可以这样证明:如果找到了元素，显然返回了它的位置，所以让我们关注未找到的情况。最终，二分搜索循环将退出，因为 low == high + 1。

让我们看看如果在这个退出之前找到元素会发生什么，考虑例如 low = high = K。然后该元素将在位置 K 处找到。既然不是，我们将设置 low = K + 1 或 high = K - 1。

由于未找到该元素，返回 low 将返回您感兴趣的内容。