Two phases in one search
Exponential search, sometimes called doubling search, suits a sorted sequence whose size is unknown or effectively unbounded, like a stream you can index but not measure. It works in two phases.
Phase one: bracket
- Start by checking index one, then two, then four, then eight, doubling each time.
- Stop at the first index whose value is greater than or equal to the target, or that runs past the end.
- Now you know the target, if present, lies between the previous index and this one.
Phase two: binary search
- Run an ordinary binary search inside that bracketed range.
- Because the range you found is at most as large as the position of the target, the second phase is bounded by the target's location, not the whole sequence.
Why it helps
- For targets near the front, you finish almost immediately, far faster than a full binary search over an enormous range.
- It removes the need to know the length up front, which is ideal for unbounded or generated data.
Key idea
Exponential search doubles a probe to bracket the target quickly, then binary searches the small window, making it ideal for sorted but unbounded data.