二进制搜索缺少的元素是否总是在它存在之前的位置之前返回该元素？

Question

这类似于lower_boundC++,二进制搜索的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

这应该是微不足道的,以适应您提到的格式的返回值.

对于这里的实现,我们可以证明这样:如果找到元素,它的位置显然会返回,所以让我们关注未找到的情况.最终,二进制搜索循环将退出,因为low == high + 1.

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

由于找不到元素,返回low将返回您感兴趣的内容.