Can you binary-search event records that are only 'mostly sorted' by timestamp?

## Why "almost" is not a weaker version of the precondition Clock skew across writers produces a log that is *nearly* ordered by timestamp: long ordered stretches with occasional local inversions where a writer running a few seconds behind appended a record whose timestamp precedes its neighbours. It is tempting to treat that as a sorted file with a small error term, and to expect binary search to be correspondingly slightly wrong. It does not degrade that way. Binary search makes about `log2 n` decisions, and **every one of them is load-bearing**. A comparison against an out-of-place record at the first probe discards half the file — potentially the half holding the target — and no later step can recover it, because the discarded region is never looked at again. One inversion in ten million rows is enough, if the search happens to land on it. The guarantee is all-or-nothing, which is why the precondition is stated as an absolute. The failure mode is also the nastiest kind operationally: - **Silent.** No exception, no diagnostic — a plausible index or a plausible "absent". - **Intermittent-looking.** Whether the search lands on an inversion depends on the target and on the current contents, so the same lookup succeeds for weeks and then misses after a late write shifts the probe path. It will be reported as a flaky read, not as a broken precondition. - **Unreproducible from the report.** By the time someone investigates, the file has changed and the failing path is gone. ## Why you cannot just check first The instinct is to verify order before searching. Verification means comparing every adjacent pair: `O(n)`. That is the same order as the linear scan you were trying to avoid, so checking-then-searching for a single query is strictly worse than just scanning — you pay the scan and then do extra work. That argument reverses completely when the check is **amortized**. Verifying once at ingest, or when a segment is sealed, costs one pass and then licenses an unlimited number of `O(log n)` lookups against that segment. The rule to carry away: *validating a precondition per query is self-defeating; validating it once at the boundary that produces the data is close to free per query.* ## The fix that does not work A plausible-sounding repair is: binary search anyway, then scan a small window around where it lands, since the displacement is bounded by the skew. Be careful — this is not sound in general. A misleading comparison can occur at **any** depth, including the very first probe, and when it does the search discards a region that is nowhere near the final landing point. The window you would have to scan is not bounded by the local displacement; the search can end up arbitrarily far from the target. Proposing this in an interview and defending it as correct is a worse answer than proposing a scan. ## The fixes that do work **Make ordering an enforced invariant.** The real defect is upstream: a file is being treated as ordered without anything guaranteeing it. Buffer arrivals behind a watermark — hold a segment open for longer than the maximum tolerated skew, order it on close, and only then publish it as searchable. Now "sealed segment" means "genuinely ordered", the check runs once, and every downstream query is entitled to halve. **Search per-writer runs and merge.** Each writer's own records are usually in order even when the interleaved stream is not. Keep or reconstruct one run per writer, binary-search each of the `k` runs independently — every one of them genuinely satisfies the precondition — and merge the `k` results. That costs `O(k log n)` instead of `O(log n)`, which is a real price but a sound one, and it is often the right answer when the streams cannot be centrally ordered. **Order by something you control.** Timestamps from skewed clocks are a poor ordering key precisely because no single party guarantees them. An ingest-assigned sequence number is monotone by construction, so searches on it are sound; timestamp queries then become a range question answered against that ordering, with the skew bound defining how far to widen the range. **Or accept the scan.** If queries are rare, `O(n)` over a segment is a perfectly professional answer, and it is correct on any input. ## What the interviewer is listening for They want to hear that you know the precondition is binary rather than statistical, that you priced the verification and noticed it costs as much as the scan, and that you moved the fix upstream to where the invariant can be enforced once rather than hoped for on every read. The weak answer is "inversions are rare, so it will be fine" — which is a claim about averages made against an algorithm that offers no average-case guarantee at all.