In exponential search over a log of unknown size, why is it safe to search up to an overshooting probe?
answer
- the search is over a predicate, not a key
- what does a read past the end answer
- false for a prefix, then true forever
- no valid maximum index is ever needed
- returning one past the end is an answer
basics
~20 sBecause reads past the last entry answer the search predicate as satisfied, the predicate stays false-then-true across the whole bracket, so a first-true binary search converges even when the upper index lies beyond the data.
solid answer
~50 sThe binary search is not looking for a key; it is looking for the first index where the predicate "this position is missing, or its key is at-or-past `T`" turns true. Past-the-end reads return a sentinel that scores that predicate true, and every real key at-or-past `T` scores true as well — so across `[bound/2, bound]` the predicate is false for a prefix and true afterwards, which is exactly what a first-true binary search needs. No clamping to a valid maximum index is required, which matters because the whole premise is that you do not know one. The index the search returns may be one past the last entry, and that is a meaningful answer: it means no entry satisfies the query yet. The bug to avoid is treating a missing entry as "key too small" — that flips the predicate back to false at the end and breaks monotonicity.
code
pseudocode · 14 linesbound = 1
while read(a, bound) != SENTINEL and key(read(a, bound)) < T
bound = bound * 2
lo = bound / 2
hi = bound
while lo < hi
mid = lo + (hi - lo) / 2
r = read(a, mid)
if r == SENTINEL or key(r) >= T
hi = mid
else
lo = mid + 1
...
return logo deeper
Remember that the upper bracket may sit past the last entry and that this is fine — a read there returns a defined 'nothing here' answer rather than breaking the search.
Be able to state the predicate and argue it is monotone: missing-or-at-or-past-target is false for a prefix and true thereafter, which is what makes the first-true binary search sound.
Show you would design the read interface for it — a defined past-the-end answer, stable ordering, and a documented meaning for a returned index that addresses no entry.
Own the contract question: whether the storage layer promises a total order and a well-defined end-of-data response decides whether this search is legal at all across every consumer of that log.
## The search is over a predicate, not over a key The habit most people carry from first learning binary search is "find the index holding this value". That framing cannot survive an input whose end you cannot see, because it gives no meaning to a probe that lands on nothing. The framing that does survive is: a binary search locates the **first index at which a monotone predicate turns true**. For "the first log entry at-or-after timestamp `T`" the predicate is: `P(i)` = "position `i` holds no entry, **or** its key is `>= T`" The `or` clause is the whole trick, and it is what makes searching up to an overshooting probe legal. ## Why that predicate is monotone Monotone means: once true, always true as the index grows — false for a prefix, true for the rest, never flipping back. Two facts give it here. First, the entries are ordered by key, so once a key is at-or-past `T`, every later key is too. Second, the missing positions are all *at the end* — a log has entries `0..n-1` and nothing after, never a hole in the middle. So the predicate reads: false, false, ..., false, true, true, ..., true, and then the past-the-end region, which the `or` clause also scores true. The sequence never returns to false. A first-true binary search over any interval whose left end is false and whose right end is true converges to the boundary in a logarithmic number of probes. The doubling phase hands over exactly such an interval: the probe at `bound/2` was observed false (that is why the loop continued), and the probe at `bound` was observed true (that is why it stopped). ## Why no clamping is needed The instinct is to write `hi = min(bound, n - 1)`. But `n` is the quantity the algorithm was built not to need — clamping would reintroduce the dependency the doubling phase exists to remove. Nothing is gained by it either: an index past the end is a perfectly probeable position under this read interface, because the interface answers "nothing here" rather than failing. The search may spend a probe or two inside the past-the-end region, and each such probe correctly pushes `hi` down. Trace the fragment: `mid` is computed as `lo + (hi - lo) / 2`, which cannot overflow the way `(lo + hi) / 2` can on a very long log, and the loop maintains the invariant that `P(hi)` is true (or `hi` is the original bracket end, known true) while `P(lo - 1)` is false. When `lo == hi`, that common index is the first true one. ## What the returned index means Three outcomes, all normal: | Outcome | Meaning | |---|---| | Returns `i` holding a key equal to `T` | The earliest entry with exactly that key | | Returns `i` holding a key greater than `T` | No entry equals `T`; this is the first one after it | | Returns an index addressing no entry | Nothing at-or-after `T` exists yet | The third is not an error and not a bug — it is the insertion point, and for a log-tailing caller it is also the offset to resume reading from once more entries land. Callers must check which case they are in before dereferencing the index, exactly as with any first-true search. Duplicates fall out for free. Because the search converges on the *first* true index, a run of equal keys is entered at its start; a search written to stop the moment it finds an equal key would instead return an arbitrary member of that run, which is the classic defect in hand-rolled binary searches. ## The mistake that breaks everything Score a missing position as "key smaller than `T`" and the predicate becomes false, then true, then false again. Binary search on a non-monotone predicate is not merely slower — it is *wrong*, and it converges silently on whichever boundary the midpoints happen to steer it toward, so the bug survives casual testing and surfaces only when a query happens to land near the end. In the doubling phase the same mistake is worse: every probe past the end would look like a reason to keep doubling, so the loop never terminates. The defensive habit is to state the predicate explicitly before writing either phase, then check the two properties out loud: is it monotone over the whole probed domain, and is it defined at every index the algorithm can probe — including the ones past the data. If either answer is no, the search is unsound no matter how carefully the index arithmetic is written.
- What does the returned index mean when no entry satisfies the query?It is the position one past the last entry — an insertion point rather than a hit. Callers must check whether the index addresses a real entry before using it, exactly as with any first-true search. For a log tailing feature that answer is useful on its own: it says "nothing new since T", and it is also the offset to resume from.
- What breaks if a missing entry is scored as 'key smaller than T' instead?Monotonicity breaks. The predicate would read false, then true across real entries at-or-past T, then false again over the past-the-end region, and a binary search on a non-monotone predicate can converge on any of the boundaries. In practice the doubling loop would also never terminate, since every probe past the end would look like a reason to keep doubling.
- How do duplicate keys interact with this search?They are handled by the same predicate. Because the search converges on the first index where 'key at-or-past T' holds, duplicates of T all sit at or after that index, and the caller gets the earliest one. A search written to stop on any equal key would return an arbitrary member of the duplicate run instead.
saying these in an interview costs you the question
- Says you must clamp the upper index to the collection size
- Claims the binary search would read out of range
- Treats a missing entry as a key smaller than the target
- Thinks a returned index past the end signals an error
- Assumes duplicates need a separate scan afterwards