Exponential search
Exponential search checks the first position, then doubles a bound — 1, 2, 4, 8, and so on — comparing the value at each new bound with the target until it finds one that is at least as large, or runs past the end of the array. That doubling finds a bracket at most twice as wide as it needs to be, and an ordinary binary search then runs inside just that bracket.
When it is the right choice
Exponential search earns its keep searching an unbounded or unindexed sequence, where finding "the end" to binary search against is itself expensive or impossible — doubling forward costs little extra over the eventual binary search, and it needs no upfront size. On an ordinary in-memory array, where the size is already known, it does the same job as binary search with a little extra bookkeeping and offers no advantage. Reframed honestly for what this tool can actually show: at a capped array size of 48, doubling from 1 needs at most six probes before it exceeds the array, so the doubling phase here is a curiosity, not the main event — the idea worth watching is the two-phase shape, bracket first, then halve.
How it works
- Check whether the target is at the very first position.
- Starting from a bound of 1, repeatedly double the bound and compare the value there with the target, stopping once that value is at least the target or the bound runs past the end of the array.
- Run an ordinary binary search for the target, restricted to the bracket the doubling just found — between half of the final bound and the final bound itself.
Worth noticing
- At the sizes this tool supports (up to 48 items), doubling from 1 needs at most six probes to run past the end of the array — this is not where the interesting cost is, and it never demonstrates the unbounded-search case exponential search is usually taught for.
- Its total comparisons are the doubling probes plus an ordinary binary search inside the bracket, so its worst case stays O(log n) — the same order as binary search, with a small constant-factor overhead in exchange for not needing to know the array length upfront.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(log n)
- Extra space
- O(1)