= Exponential search
<Exponential search> locates a target's possible range in a sorted sequence by probing indices $1,2,4,8,\ldots$ until the target is bounded above or the sequence ends, then uses <binary search> inside the final bracket. If the target lies near index $k$, this takes $O(\log(k+1))$ probes under random-access and constant-comparison assumptions. For an unbounded monotone predicate, the same method brackets the first true index. It is useful when the relevant prefix is much shorter than the whole sequence or its length is not initially known. Finite sequences still require bounds checks at each probe.
Back to article page
