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

Question

The following is a slightly modified implementation of binary search that finds the first occurrence of an Integer key.

Is this still O(log n)? I'm having some trouble determining whether this becomes O(n) in the worst case.

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;
}

My apologies, I've been looking at it for so long that I forgot it wasn't obvious. The third if block (lo < mid). — albertjorlando, Dec 29 '17 at 16:44
@OliverCharlesworth I believe the 3rd conditional statement is the addition. — hnefatl, Dec 29 '17 at 16:44
To find the first occurrence of the key as stated in the description — albertjorlando, Dec 29 '17 at 16:47
First step: profile it with test-data of different sizes to get an educated guess about the complexity — MrSmith42, Dec 29 '17 at 17:24
Not the best way to do that job. See: https://stackoverflow.com/questions/46795712/binary-search-for-first-occurrence-of-k/46796136#46796136 — Matt Timmermans, Dec 30 '17 at 20:36

ubadub · Accepted Answer · 2017-12-29T17:06:02.793

Yes, it is still O(log(n)). The third conditional statement only runs if key.compareTo(a[mid]) == 0 (because the previous two conditionals eliminate the inequality cases) and if lo < mid.

If the key exists exactly once in the array, this branch will happen at most once; if the key does not exist, it will not happen at all. Since the conditional itself as well as everything in the body of the conditional is a constant time operation, the running time remains O(log(n)).

What if the key occurs multiple times? First, what's the purpose of this conditional branch anyways:

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

If lo < mid, it means we haven't scanned the full range of the list. Thus, we set hi = mid, thereby establishing mid as the upper bound for our search.

Thus, even if the key occurs multiple times, the search range is halved at every iteration.

That branch can occur more than once. Consider `a = { 5, 5, 5, 5, ... }`, `key = 5`. — Oliver Charlesworth, Dec 29 '17 at 16:55

score 1 · Answer 2 · answered Dec 29 '17 at 17:06

Assuming we model individual statements as O(1), then our overall complexity is dictated by the number of loop iterations.

The number of iterations can only be O(n) if we're reducing the range ([lo, hi)) by a constant amount per iteration (on average). In all three relevant cases, it should be evident that that's not the case - the range is always halving, on average.

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

2 Answers2