the sorted-search lower bound

Binary search finds a target in a sorted array of n items using about log2(n) comparisons, halving the range each step. It feels hard to beat — but is it truly optimal, or could a cleverer comparison strategy find things faster? The sorted-search lower bound answers: no comparison-based search can do better than Omega(log n) comparisons in the worst case. Binary search is not merely good; it is the best possible in its model.

The argument is the same decision-tree counting idea, now for searching. Think about searching for a value that is NOT necessarily present: the algorithm must, in the end, report which 'gap' the target falls into, or which position it matches. With n sorted elements there are n possible match positions plus n+1 gaps between and around them, so there are at least n+1 distinct answers the search might have to return. Model the comparison-based search as a binary decision tree: every distinct answer needs its own leaf, so the tree has at least n+1 leaves, hence height at least log2(n+1). Since the worst-case comparison count is the tree's height, it is at least log2(n+1) = Omega(log n). Each comparison yields at most one bit (yes/no), so you cannot distinguish n+1 outcomes in fewer than log2(n+1) questions.

The same scoping caveats apply as for sorting. This is a comparison-model statement: it does not forbid faster searches that use the key's value, such as hashing (expected O(1) lookups) or interpolation search (about O(log log n) comparisons on uniformly distributed keys, by guessing where the target should be instead of always halving). Those exploit information beyond order, so they leave the comparison arena. Within pure order comparisons, though, Omega(log n) is a true floor, and binary search's O(log n) sits exactly on it, giving Theta(log n).