Module 6
Searching & sorting
Binary searchis the purest algorithm you'll be asked to write, and the most commonly botched. The idea is trivial — on sorted data, probe the middle, discard the half that can't contain the target — and the discipline is everything: a precise invariant(“the answer, if present, is always within [lo, hi]”), inclusive bounds, while lo <= hi, and moving to mid ± 1 so the range strictly shrinks. Drift from any of those and you get the famous infinite loop or off-by-one. State the invariant out loud and the code writes itself.
Its reach is bigger than “find x in an array”: binary search works on any monotonic predicate— first version that fails, smallest capacity that ships in time, boundary of true/false. If you can answer “is mid enough?” in O(n), you can often solve the whole problem in O(n log range).
🎛 Binary search, probe by probe
Faded cells are eliminated without being looked at — each probe halves the live range, which is why 12 elements take at most 4 probes and a billion take 30. Try 50 to watch the search prove absence.
Sorting you'll mostly userather than implement — but you're expected to know the landscape, and merge sort's recursive shape (split, sort halves, merge in O(n)) is fair game to write. Comparison sorts can't beat O(n log n) in general; counting-based sorts sidestep that bound when keys are bounded integers. Stability — equal elements keeping their original order — matters the moment you sort by one field after another.
| Sort | Typical | Worst | Space | The one thing to say |
|---|---|---|---|---|
| Quicksort | O(n log n) avg | O(n²) worst | O(log n) | fast constants; worst case on adversarial pivots; not stable |
| Merge sort | O(n log n) | O(n log n) | O(n) | guaranteed bound, stable; the extra array is the price |
| Heapsort | O(n log n) | O(n log n) | O(1) | in-place + guaranteed; slower constants, not stable |
| Insertion sort | O(n)–O(n²) | O(n²) | O(1) | wins on tiny or nearly-sorted input; real libraries use it as the base case |
| Counting/radix | O(n + k) | O(n + k) | O(k) | beats n log n by not comparing — needs bounded integer-like keys |
“Sort first” as an optimization move
Many O(n²) problems become O(n log n) by paying for one sort up front: duplicate detection (sort, scan neighbors), two-sum on sorted data (two pointers walking inward), merging intervals (sort by start, sweep). When you're stuck at quadratic, ask the standard question: “does sorting unlock a linear pass?”— it's the second-most-common unlock after a hash map, and unlike the hash map it costs no extra memory beyond the sort.
Say it out loud
- “Invariant: the target, if present, lives in [lo, hi]. Loop while lo ≤ hi, move past mid each time — that guarantees termination.”
- “The data's sorted — that's a loud hint toward binary search or two pointers.”
- “I'll use the library sort — O(n log n) — and spend my time on the scan that follows it.”