Exponential Search
Double a probe index until you overshoot, then binary-search the last doubling — O(log i) where i is the target's position, not the array's size.
Hands on Interactive visualization
Implementation Code
export function exponentialSearch(a: number[], target: number): number {
const n = a.length;
if (n === 0) return -1;
if (a[0] === target) return 0; // doubling starts at 1
let bound = 1;
while (bound < n && a[bound] < target) bound *= 2; // zoom out
// Binary search the bracket [bound/2, min(bound, n-1)].
let lo = bound >> 1;
let hi = Math.min(bound, n - 1);
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (a[mid] === target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Big-O Complexity
i is the target's index: ~log i doublings to bracket it plus a binary search over a window of size ~i. For targets near the front this handily beats a full O(log n) search.
In production When to use
Searching a sorted stream, an infinite conceptual array, or an API that only exposes get(i) with no length: doubling probes find a finite bracket without ever knowing n.
Recent-first sorted logs, priority queues drained from one end, leaderboards queried near the top — when i is much smaller than n, O(log i) is a real saving over O(log n).
TimSort's galloping mode (Python's sorted, Java's Arrays.sort for objects) is exponential search: when one run keeps winning a merge, it doubles ahead to find how far the streak extends.
Intersecting or merging a small sorted list against a huge one: exponential-search each small element into the big list for O(m log(n/m))-style bounds instead of m full binary searches.
When each probe is a network call or page fetch against sorted remote data of unknown extent, doubling finds the relevant page range in a logarithmic number of round-trips.
Trade-offs Strengths & weaknesses
- Runs on unbounded or unknown-length sorted data — no n required up front.
- O(log i) adapts to the target's position: near-front targets are found almost instantly.
- O(1) extra space; the binary-search phase is ordinary and well-understood.
- The engine behind TimSort's galloping merge optimization.
- Never worse than binary search by more than a constant factor (~2x the probes).
- Still requires sorted input, like every order-exploiting search.
- For uniformly placed targets it is just binary search with extra bracketing probes.
- Index doubling can overflow fixed-width integers on adversarially long data if unguarded.
- The bounded-array version needs careful clamping of the bracket to n - 1.
- Two phases mean two places to plant off-by-one bugs.
Intuition Mental model
Zooming out to find the right page range
You are looking for a word in a book with no page count and no index. You check page 1, then 2, 4, 8, 16 — zooming out in powers of two — until you land past the word. Now you know exactly which doubling contains it, and you binary-search just that span.
- Peek at page 1 first — the doubling never revisits the very start.
- Double the page number until the page you open is past the target word.
- The word now provably lives between the last two probes: [bound/2, bound].
- Binary-search only that bracketed span — it holds about as many pages as the target's position.
- Total work tracks where the word is, not how thick the book might be.
Prep Interview questions
How do you search a sorted array whose length you cannot know?
Why is the total cost O(log i) and not O(log n)?
Where does galloping appear in TimSort, and why?
Exponential vs jump search: both bracket then scan. When does each win?
What breaks if you binary-search [0, bound] instead of [bound/2, bound]?
Watch out Common bugs
After the doubling loop exits with bound >= n, the binary search must run on [bound/2, min(bound, n - 1)]. Using bound directly indexes out of bounds.
The doubling loop starts at 1, so a target at index 0 is never probed by it. Check a[0] explicitly first — the classic silent miss.
bound *= 2 on a fixed-width integer wraps negative past 2³⁰-ish elements if not bounds-checked before the multiply. Check bound < n before doubling, or use a wider type.
The target can sit exactly at bound/2 or at bound. Binary-search the closed range [bound/2, min(bound, n-1)] — shaving either endpoint drops legitimate hits.
One screen Cheat sheet
Double an index to bracket the target, then binary-search the final [bound/2, bound] window.
- The search for sorted data of unknown or unbounded length.
- Cost scales with the target's position i, not the array size n.
- Check index 0 explicitly — the doubling loop starts at 1.
- Clamp the final window to [bound/2, min(bound, n - 1)].
- This is TimSort's galloping mode during lopsided merges.
- Roughly 2·log i probes total: log i to bracket, log i to binary-search.