How does exponential search find a search range on a sorted input of unknown size?
answer
- binary search needs a high bound first
- you cannot ask this input its length
- probe further and further out
- 1, 2, 4, 8, 16 until you overshoot
- then search between the last two probes
basics
~20 sIt probes index 1, then 2, 4, 8 and so on until a probe reaches or passes the target or falls off the end, then binary searches only the interval between the previous probe and that one.
solid answer
~40 sExponential search runs in two phases. The **doubling (galloping) phase** probes indexes 1, 2, 4, 8, 16... until a probe either lands on a key at-or-past the target or reads past the last entry; that gives an upper bracket without ever asking the collection how long it is. Because the probe before it was still below the target, the answer must lie in `[bound/2, bound]`, so the **second phase** is an ordinary binary search over that interval only. The doubling phase discovers the size — that is the whole point. It needs the same precondition as binary search: the keys must be sorted (or the predicate you are searching must be monotone), and probing an arbitrary index must be possible.
go deeper
Be ready to say the two phases out loud: double the probe index until you overshoot, then binary search the interval you just jumped over. Mention that the input must still be sorted.
Explain why the bracket is [bound/2, bound] — the previous probe was below the target — and that the doubling phase is itself the size discovery, not a separate scan.
Expect to be asked where this shows up for real: sorted stores whose size is expensive or stale to query, and reads where each probe is a round trip rather than a memory access.
Own the framing that the size query is a dependency, not a free fact. Choosing a search that never needs it can remove a coordination point from a read path entirely.
## The problem it solves Binary search needs two index bounds before it can compute a midpoint. A low bound is free (0). The high bound is not: on an append-only, replicated event log there may be no cheap way to ask "how many entries are there?" — the count may require a coordination round trip, may be stale on a follower, or may simply not be exposed. All you can do is read entry `i` and get either a record or a sentinel meaning "past the end". Exponential search removes that dependency. It manufactures a high bound by probing, and it does so in a number of probes proportional to the logarithm of where the answer actually is. ## The two phases **Phase 1 — doubling (also called galloping).** Start with `bound = 1`. While the entry at `bound` exists and its key is still below the target `T`, set `bound = bound * 2`. The loop stops the first time the probe overshoots: either `key(bound) >= T`, or the read returned the past-the-end sentinel. **Phase 2 — binary search.** The previous probe, at `bound/2`, was strictly below `T`; the current probe at `bound` is at-or-past it. So the first entry with key `>= T` lies in `[bound/2, bound]`, an interval of length `bound/2`. Run a standard first-true binary search there. Starting at 1 rather than 0 matters: doubling 0 stays 0 forever. Index 0 is not skipped — it is the low end of the very first bracket, `[0, 1]`, when the first probe already overshoots. ## Why the bracket is correct The correctness argument is the monotone-predicate argument, not an "array of numbers" argument. Define `P(i)` = "entry `i` is missing or its key is `>= T`". Because keys are non-decreasing and the missing entries are all at the end, `P` is false for a prefix and true for the rest — it never flips back. The doubling loop stops at the first probed index where `P` is true, and the last index where `P` was observed false is `bound/2`. Binary search inside `[bound/2, bound]` is then searching a range whose left end is false and whose right end is true, which is exactly the shape a first-true binary search requires. This is why the technique is not restricted to arrays of keys: any random-access, monotone domain works — a log addressed by sequence number, a function evaluated at integer points, a paged remote store. ## What it costs If the answer sits at position `i`, the doubling phase makes about `log2(i)` probes (it stops at the first power of two at or beyond `i`), and the binary search runs over an interval of size at most `i`, another `log2(i)` probes. Total: `O(log i)` — **output-sensitive**, expressed in where the target is, not in how big the collection is. Finding the first entry after a recent timestamp in a log with a trillion entries costs a couple of dozen probes if that entry is near the head, and it costs that whether the log has a million entries or a trillion. ## The preconditions people forget - **Sorted / monotone.** Doubling does not rescue you from unsorted data; both phases assume order. - **Random access by index.** Every probe must be roughly equally reachable. Chasing links one node at a time to reach index 8, then 16, then 32 destroys the bound — the walking dominates. - **A defined "past the end" answer.** Something must distinguish "no entry here" from "entry with a small key". A sentinel value, an out-of-range signal you catch, or an explicit end marker all work; the algorithm just needs the predicate to be answerable at every probed index. ## What it is not It is not linear scanning with bigger steps that then "fixes up" the answer, and it is not a way to search unsorted data. It is also not automatically better than plain binary search: when the size is cheaply known and the target is uniformly placed, plain binary search does about `log n` probes while exponential search does about `2 log n` in the worst case. Its wins are the unknown-size case and the case where targets cluster near the front.
- Why does the doubling start at index 1 instead of index 0?Because doubling zero stays zero — the probe would never advance. Index 0 is still covered: if the very first probe at index 1 already overshoots the target, the bracket handed to the binary search is `[0, 1]`, so position 0 is inside the searched range.
- What if reading past the last entry raises an error instead of returning a sentinel?Treat that error as the sentinel: catch it and score the predicate as true, meaning "at-or-past the target". The algorithm only needs a way to answer "is index i at-or-past what I want?" at every probed index; whether the answer arrives as a value or as a signal is immaterial to the bracket and to the bound.
- Does exponential search work if the input is not sorted?No. Both phases rely on the searched predicate being monotone — false for a prefix, then true for the rest. On unsorted data an overshooting probe tells you nothing about what lies before it, so the bracket is meaningless and the binary search inside it is unsound. Unsorted input leaves you with a linear scan.
Looking for a house number on a very long street with no map: you check number 1, then 2, then 4, 8, 16 until you pass it, then you only have to search the block you just jumped over.
saying these in an interview costs you the question
- Says you must know the length before any binary search
- Describes it as scanning forward one element at a time
- Thinks the doubling phase alone costs linear time
- Claims it works on unsorted input
- Starts the doubling at index 0 and never advances