Sorted input is a cue, but which patterns does it license, and what decides between them?

## The cue and the three families "The input is sorted" is the single most over-read cue in coding interviews, and the standard wrong answer is "sorted means binary search." Sortedness is not a pattern; it is an **invariant** — for any position, everything to the left is no larger and everything to the right is no smaller. What you can do with that invariant depends entirely on the ask. **Family 1 — converging pointers (the ask is a pair or a combination).** Place one index at each end. Evaluate the current pair against the target relation. Because the sequence is ordered, a single comparison proves that one of the two current endpoints cannot participate in any better pair, so you retire it and move inward. Example ask, in an original setting: a shipping manifest is ordered by crate weight, and you want the pair of crates whose combined weight comes closest to the container's remaining capacity without exceeding it. If the current pair is over capacity, the heavy end cannot pair with anything lighter than the current light end and still improve, so it moves inward; otherwise you record the candidate and advance the light end for a bigger total. Each index moves at most n steps, giving O(n) time and O(1) extra space. Extending to a three-crate combination is the same idea with an outer loop: O(n^2), not O(n^3). **Family 2 — binary search (the ask is a boundary).** Use it when the question is *where does a property start being true*: the first crate at or above a weight, the count of entries below a threshold (found from two boundaries), or the smallest capacity that makes a whole plan feasible. The last case matters more than candidates expect: binary search needs a **monotone predicate**, not a stored sorted array. If "capacity C works" implies every larger capacity works, you can binary search the answer space itself, calling a feasibility check as the comparison. That is where the pattern earns its keep beyond simple lookup. **Family 3 — a merge pass (the ask combines two ordered sources).** Two ordered manifests, and you want their combination, their overlap, or a rank statistic across both. Advancing whichever front element is smaller costs O(n + m); re-sorting the concatenation costs O((n+m) log(n+m)) and throws away the order you were handed. ## What actually decides The **shape of the ask** decides: - pair / triple / combination against a target relation → converging pointers; - first-or-last position satisfying a monotone property, or a numeric answer with a feasibility test → binary search; - two or more ordered sources to reconcile → merge. Two further checks separate a middle answer from a junior one: **Sorting is not free, and it destroys information.** If the input is *not* already sorted, choosing a sorted pattern means paying O(n log n) up front. For an existence question like "do two entries stand in this exact relation," a single pass with a hash map of seen values answers it in expected O(n) — sorting is then a downgrade unless you need ordered output, unless you must avoid the hash map's memory, or unless you need a worst-case guarantee that hashing does not give you (hash operations are expected O(1), degrading to O(n) per operation under adversarial collisions). Sorting also destroys the original positions: if the answer must be reported as positions in the input, you must carry them along explicitly. **Binary search needs random access.** Halving assumes you can jump to the middle in constant time. An ordered sequence you can only traverse one link at a time gives you converging pointers only if you can reach both ends cheaply, gives you a merge pass, and gives you no halving at all — the jump to the midpoint is itself linear, which cancels the benefit. "Sorted, therefore binary search" quietly assumes an access model the statement may not have granted. ## Duplicates and the boundary you actually want With repeated keys, "find the entry equal to x" is under-specified: you usually want the *first* position at or above x, or the *first* position strictly above x. Writing the search to return a boundary rather than an arbitrary match makes counting, range extraction and insertion-point queries fall out of the same routine, and it removes the most common off-by-one in the pattern. Say which boundary you are computing before you write the loop. ## The interview answer When an interviewer plants "the input is sorted" in the statement, they are testing whether you treat it as a verdict or as a resource. The strong answer names the family the *ask* selects, states the cost of the alternative that ignores sortedness, and flags the access-model assumption. That is a thirty-second narration and it distinguishes practiced recognition from memorised solutions.