When is a rotation-aware search not worth shipping, and what would you build instead?

## The decision, not the algorithm By the time this comes up you can already write the search. The question is whether it belongs in the system, and it is asked because the reflex answer — "logarithmic beats linear, obviously ship it" — skips every consideration that actually governs the call. ## What the clever version costs Rotation-aware search is perhaps fifteen lines, and every one of them is a place to be subtly wrong: - The ordered-side test must be anchored on the right endpoint and written with the right strictness. - The membership test needs asymmetric inclusivity, or targets sitting on a boundary are lost. - A midpoint-keeping shrink must be paired with a strict loop condition, or the code hangs instead of answering. - Repeated keys silently degrade the bound to linear with no error and no log line. - Every one of these failures is *quiet*. Nothing throws; the caller gets a wrong answer or a slow one. That profile — quiet wrongness, thin test coverage in practice, review that is hard to do carefully — is the real cost, and it is paid every time someone touches the code for the next several years, not once at implementation. ## What it buys A logarithmic bound instead of linear. Sizing it matters: on a 4,096-entry capture buffer, a scan is a few thousand comparisons and a dozen for the search. Both are far below the cost of formatting the crash report the lookup feeds. If the lookup happens once per crash, the improvement is unmeasurable. If it happens per-record inside a hot replay loop over millions of entries, it is the difference between a feature and an outage. So the first two questions are always **how large is the range** and **how often is it queried**, and the third is **what else is on the critical path**. ## The alternatives that usually win **Record the wrap position at write time.** The component that wraps the buffer knows its own head index. Persisting it alongside the data turns every later lookup into an ordinary search over positions remapped by one modulo, and the entire rotation-aware branch structure evaporates. This is nearly always the right call when you own the writer, and the reason it gets overlooked is that the interview framing hands you the array as a given. **Normalise once on read.** If reads dominate writes, rotate the dump into true order once — a linear pass — and every subsequent query is an ordinary search. The linear cost is paid once and amortised across the read traffic. This is the standard read-mostly argument, and it also removes the duplicate-key degradation. **Just scan.** For small ranges queried rarely, the scan is correct by inspection, obviously right in review, immune to the duplicate case, and fast enough. Choosing it deliberately, with the numbers stated, is a stronger answer than choosing it out of ignorance. ## When the rotation-aware search is genuinely right It wins when normalising is not available and the range is big: shared or memory-mapped storage you must not copy; an immutable snapshot; a fleet-wide memory ceiling that forbids a second copy of a large range; a producer you do not own and cannot make record its head; or query volume high enough that a linear scan shows up in a latency budget. In those situations, ship it — and then invest in the thing that makes it safe: a test that enumerates every rotation offset of a small range including zero, plus the repeated-key case, so the quiet failure modes are loud in the build instead of in production. ## Team and maintenance angles Two more inputs a lead is expected to weigh. First, **who maintains it**: an invariant-heavy fifteen lines is fine in a team that reviews algorithmic code confidently and a liability in one that does not; the mitigation is a comment stating the invariant in words plus the exhaustive small-input test, not a hope that the next reader reconstructs it. Second, **where else the shape appears**: if wrapped ranges show up in three components, one reviewed utility with real tests beats three hand-rolled copies, and that consolidation argument can flip a marginal call toward building it properly once. ## What a strong answer sounds like It names the numbers before the asymptotics, proposes removing the rotation at the source, states the specific conditions under which it would still ship the clever search, and commits to the test strategy that makes the quiet failure modes visible. What it does not do is treat the complexity class as the whole argument.