Introduction

For a plain sorted array searched by comparisons, O(log n) is the right asymptotic target and binary search meets it. The reason is not that nobody has been clever enough to do better. It is that every comparison gives only limited information, and identifying one target position among n ordered possibilities requires about log2(n) bits of information. That is the comparison-based lower bound.

The Decision-Tree View

Any comparison-based search algorithm can be represented as a decision tree.

At each step, the algorithm compares the target with some array value and branches based on the result. In the simplest model, each comparison tells you whether the target is:

• less than the probed value
• equal to the probed value
• greater than the probed value

To decide whether the target is present and where it belongs, the algorithm must distinguish among many possible outcomes. A shallow tree simply does not have enough leaves to represent all cases.

That is why search time cannot beat logarithmic growth in the comparison model.

Why Binary Search Matches the Lower Bound

Binary search works by halving the remaining candidate range after each comparison.

1
2def binary_search(values, target):
3    lo = 0
4    hi = len(values) - 1
5
6    while lo <= hi:
7        mid = (lo + hi) // 2
8        if values[mid] == target:
9            return mid
10        if values[mid] < target:
11            lo = mid + 1
12        else:
13            hi = mid - 1
14
15    return -1
16
17
18print(binary_search([3, 7, 10, 14, 20, 31], 14))
19print(binary_search([3, 7, 10, 14, 20, 31], 8))

After one comparison, about half the array is impossible. After two comparisons, about three quarters is impossible. After k comparisons, the candidate set is reduced by roughly a factor of 2^k.

So after about log2(n) comparisons, only one candidate position remains. That is why binary search is optimal in the comparison model.

A Simple Lower-Bound Argument

Suppose an algorithm uses at most k comparisons. Then its comparison tree can distinguish at most about 2^k binary branches worth of outcomes. But a sorted array of length n has n possible hit positions plus at least one miss outcome, and more precisely n + 1 insertion gaps for misses.

To distinguish all those cases, you need:

2^k >= n + 1

Taking logs gives:

k >= log2(n + 1)

That is the essence of the lower bound. No comparison-only algorithm can guarantee better asymptotic worst-case performance on a sorted array.

What This Claim Does Not Mean

The statement needs careful scope. It does not mean every imaginable search problem is stuck at O(log n) forever.

You can do better if you change the model, for example by allowing:

• preprocessing into a hash table
• extra index structures
• assumptions about numeric distribution, as in interpolation search
• machine-word tricks and specialized RAM-model structures

But those are no longer the same problem as "search this plain sorted array using only comparisons."

That distinction matters a lot. Lower bounds are always about a model, not about all possible worlds.

Why O(1) Lookup Elsewhere Does Not Contradict This

People often ask: if hash tables can do expected O(1) lookup, why not a sorted array?

Because a hash table is not just a sorted array. It uses extra structure and a different access strategy. The lower bound here applies to comparison-based search over the ordered array representation itself.

Likewise, if you preprocess the array into a search tree, perfect hash, or multi-level index, query time can change. But the preprocessing and extra storage become part of the solution.

Why Random Probing Does Not Help Asymptotically

Trying random positions or a more "creative" probing order does not beat the lower bound in the worst case. You still need enough comparisons to eliminate enough possibilities.

The best you can do asymptotically, without extra assumptions, is still logarithmic.

That is why interview answers that say "maybe there is a smarter probe order" miss the real issue. The limit is informational, not stylistic.

Common Pitfalls

The biggest mistake is stating the lower bound without the phrase "comparison-based." Without that qualifier, the claim is too broad.

Another mistake is confusing worst-case lower bounds with average-case claims under special data distributions. Interpolation search can be faster on some distributions, but it does not invalidate the general comparison-model bound.

Developers also sometimes forget the miss case. A search algorithm must distinguish absence as well as exact hits.

Finally, do not mix preprocessing-heavy data structures into a claim about a plain sorted array. Those are different problem setups.

Summary

• For a plain sorted array searched by comparisons, O(log n) is the optimal worst-case bound.
• Binary search achieves that bound by halving the candidate range after each comparison.
• The lower bound comes from the amount of information needed to distinguish all possible outcomes.
• Faster lookups are possible only when you change the model with preprocessing, extra memory, or stronger assumptions.
• The correct statement is not "search can never beat O(log n)," but "comparison-based search on a sorted array cannot beat it asymptotically."