Why does binary search lose its O(log n) advantage on a sorted linked structure?

## Two preconditions, not one Almost everyone can recite that binary search requires sorted data. The second precondition is quieter and is what this question is really about: **the algorithm must be able to reach the middle of a range at roughly the cost of reaching any other position.** That is what random access means — index arithmetic gets you to a position directly, without visiting the positions in between. A contiguous, index-addressable layout gives you exactly that: computing a midpoint is arithmetic on two bounds and reading it is a single access. A linked layout does not. Its elements know only their neighbours, so the only way to arrive at position `k` is to start at an end and follow `k` links. ## The cost, done properly Suppose the data is ordered but linked, and you insist on running the halving loop anyway. Start with `n` nodes: - to reach the midpoint of the whole structure you walk about `n/2` links, then compare; - the surviving half has `n/2` nodes, and reaching *its* midpoint costs about `n/4` links; - then `n/8`, then `n/16`, and so on. Total traversal work is `n/2 + n/4 + n/8 + ... ≈ n`. The geometric series converges to `n`, so the search costs Θ(n) — asymptotically identical to just scanning from the front. Notice the shape of the answer carefully, because stating it precisely is what earns the point: the **comparison count is unchanged**, still about `log2(n)`. Halving genuinely happens. What collapses is the assumption that a probe is free. Binary search on a linked structure is a logarithmic number of expensive probes, and the probe cost is what dominates. A scan is not merely as good asymptotically — it is better in practice. It touches each node once in link order rather than repeatedly re-walking prefixes, it needs no bookkeeping, and on ordered data it can stop the moment it passes where the target would have been. So the halving loop here is strictly worse: same asymptotics, more code, more work, no early exit. ## What the general rule is The transferable statement is: **binary search's O(log n) is a bound on probes, and it translates into an O(log n) *running time* only when a probe is O(1).** Any layout that makes midpoint access more expensive changes the answer, and the correction is not subtle — it is the difference between logarithmic and linear. This is worth internalising because the same reasoning shows up whenever the ordered data is not sitting in fast, index-addressable memory. If a probe costs a distant access, the count still matters but the *cost per probe* becomes the thing to optimise, and the right response is usually to change how the data is laid out rather than to change the search. ## Getting logarithmic search back over linked data If the data must live in nodes — because insertions and deletions in the middle have to stay cheap, say — then you restore fast search by adding a way to skip rather than by cleverness in the loop: - a **balanced search tree** replaces positional halving with structural halving: the ordering is encoded in the shape, so each step descends one level instead of walking a prefix; - a **skip list** keeps the linked form but layers express lanes over it, so a search can jump many nodes at a time and then drop down a level; - an **auxiliary index** — a compact ordered array of keys plus references into the nodes — gives you a random-access surface to binary-search, at the cost of keeping it in sync with updates. All three are the same move: buy back the ability to skip. None of them is a change to the halving loop itself, which is precisely the point — the loop was never the problem. ## The interview failure modes The weak answers cluster in three places. First, "sorted is enough" — reciting the sortedness precondition and stopping. Second, claiming the comparison count degrades to `n`; it does not, and saying so shows the candidate is guessing rather than reasoning about where the work goes. Third, quoting `O(n log n)` by multiplying `log n` probes by an `n`-cost probe — plausible-sounding but wrong, because the probes get cheaper as the range shrinks, and the series sums to `n` rather than `n log n`. A crisp answer names the missing precondition, does the geometric sum out loud, separates comparison count from traversal cost, and finishes with what you would actually do instead.