How do duplicate values change the worst case of searching a rotated sorted array?

## Where the logarithm actually comes from A rotated-range search is logarithmic for one reason: every iteration proves something about where the single wrap point is, and that proof discards half the range. The proof is the endpoint comparison — `a[mid]` versus `a[hi]`, strictly greater or not. With distinct values that comparison is a clean dichotomy. Allow repeated values and a third case appears: `a[mid] == a[hi]`. Now the comparison proves nothing. Consider a run of equal keys with one smaller key hidden inside it: the smaller key may lie to the left of the midpoint or to the right, and both configurations produce identical values at `lo`, `mid` and `hi`. No amount of cleverness inside that window resolves it, because the information genuinely is not there — this is an information-theoretic limitation, not a weakness of a particular implementation. ## The standard remedy and its cost The accepted fallback is to give up half-range elimination for one step and shrink by a single position — typically `hi = hi - 1` when the tie occurs (safe because `a[hi]` is equal to `a[mid]`, which is still in the window, so nothing unique is lost). Correctness is untouched; the range still contains the answer, and it still shrinks, so the loop terminates. What is lost is the bound. A window like `5 5 5 5 5 1 5 5 5` forces the linear step repeatedly, and the search degenerates to a scan: Θ(n) in the worst case. Concretely, a capture buffer full of identical heartbeat values with a single interesting record wrapped inside it is exactly this adversarial shape — and it is not contrived, because heartbeat-style padding is common in real capture buffers. ## Direction discipline on this claim Three precise statements are worth rehearsing, because interviewers probe each one: - **O(n) is the worst case, not the expected case.** On data with reasonable key variety the tie condition is rare and the observed behaviour stays close to logarithmic. Saying "duplicates make it linear" without qualification overstates it in the other direction. - **Worst case is not amortised.** There is no sequence-averaging argument that rescues the bound: one single query on adversarial data costs linear time. This is not the amortised-doubling situation where expensive steps are paid for by cheap ones. - **The result is still right.** Weak candidates say duplicates "break" the search. They degrade it. A search that returns a wrong index on duplicates has a different bug. A further subtlety: with duplicates, "the" answer may not be unique. If the question is *is this key present*, any matching index will do. If the question is *the first matching index*, or *the position of the wrap point when several entries tie for smallest*, the specification must say which one you owe, and the tie-breaking costs extra work. Nail that down before writing anything. ## What a senior actually does about it The interesting answer is rarely a cleverer search. Options, roughly in order of how often they are the right call: 1. **Remove the rotation from the read path.** If the writer knows where it wrapped, have it record that index. Lookups then become ordinary searches over remapped indices, and the duplicate problem stops mattering for the structural decision entirely. 2. **Make the keys distinct.** Sequence numbers, monotonic timestamps with a tiebreaker, or a composite key restore the dichotomy that the logarithm depends on. 3. **Accept the linear worst case explicitly.** For a few thousand entries, a linear scan is microseconds; document the bound and move on rather than shipping a subtle search whose bad case is rare enough to escape testing and show up in production. 4. **Detect and bail.** If ties are observed, switch to a scan of the current window rather than iterating the one-step shrink — same asymptotics, simpler code, no surprising loop behaviour. ## The interview trap The question is usually posed as a follow-up: you present a clean logarithmic solution, and the interviewer says "what if values can repeat?". The wrong answer is "it still works, still O(log n)". The complete answer names the tie case, states what information is missing, gives the one-step shrink as the remedy, states Θ(n) as the resulting worst case while noting correctness is preserved and typical behaviour is unaffected, and then — the part that separates senior from middle — proposes changing the data or the write path instead of the search.