Exponential Search

Exponential search finds the neighborhood before it pins down the address. Starting at index one, it doubles a bound — 1, 2, 4, 8, 16 — checking only the value at each stop, until that value finally reaches or passes the target. Two things are true the moment it stops: the target sits somewhere in the last doubling, between the previous bound and the current one, and it got there in about log n steps without ever looking at most of the array.

That brackets the target inside a range of known size, and the second phase is just an ordinary binary search over that range — another log n steps. So the whole thing is O(log n), same as binary search on the full array. The reason to reach for it is the first phase never probes far past the target’s actual position, so on a huge or even unbounded list a target near the front is found in time that scales with where it is, not with how long the list is. That also makes it the standard front end for searching an unbounded stream, where you do not know the length to hand binary search in the first place.

Watch the lit window balloon outward as the bound doubles, then snap to the bracketed range and halve inward the way binary search does. Type a value into the search box to look for something specific, or leave it empty and let the Target menu pick one that is present or falls in a gap. Data switches between numbers and words, and New array deals a fresh sorted set.