这个修改后的二分搜索实现仍然是 O(log n) 吗？

Question

以下是查找第一次出现的 Integer 键的二分查找实现的略微修改。

这还是 O(log n) 吗？ 我很难确定在最坏的情况下这是否变成 O(n)。

private static Integer lowestRank(Integer[] a, Integer key) {
    Integer lo = 0;
    Integer hi = a.length - 1;

    while (lo <= hi) {
        Integer mid = lo + ((hi - lo) / 2);
        if (key.compareTo(a[mid]) > 0) {
            lo = mid + 1;
        } else if (key.compareTo(a[mid]) < 0) {
            hi = mid - 1;

        // Modified here to return the first occurrence of the key, if it exists
        } else if (lo < mid) {
            hi = mid;

        } else {
            return mid;
        }
    }

    return -1;
}

Answer 1

对，还是O(log(n))。第三个条件语句仅在 key.compareTo(a[mid]) == 0（因为前两个条件消除了不等式情况）和 lo < mid.

时运行

如果键在数组中只存在一次，则该分支最多发生一次；如果密钥不存在，则根本不会发生。由于条件本身以及条件主体中的所有内容都是恒定时间操作，因此运行时间保持 O(log(n)).

key出现多次怎么办？首先，这个条件分支的目的是什么：

else if (lo < mid) {
    hi = mid;
}

如果lo < mid，则表示我们还没有扫描列表的全部范围。因此，我们设置 hi = mid，从而将 mid 作为我们搜索的上限。

因此，即使key出现多次，搜索范围也会在每次迭代时减半。

Answer 2

假设我们将单个语句建模为 O(1)，那么我们的整体复杂度取决于循环迭代次数。

迭代次数只能是 O(n) 如果我们每次迭代将范围 ([lo, hi)) 缩小一个常数（平均） .在所有三个相关案例中，显然情况并非如此 - 范围总是平均减半。

这个修改后的二分搜索实现仍然是 O(log n) 吗？

Is this modified implementation of binary search still O(log n)?

java

algorithm

binary-search