A First Taste of Algorithms · Two Questions
Structure buys speed
Suppose the list is sorted: arranged in order, smallest to largest, A to Z. What did that arrangement buy?
Everything. A sorted list answers the guessing game’s magic question. Check the middle item. If it equals the target, done. If the target is bigger, then — because the list is sorted — the target cannot live anywhere in the left half. Discard half the list without looking at it. If smaller, discard the right half. Repeat on whatever survives.
This is binary search, and the phrase to underline is without looking at it. Linear search pays one step per item examined and learns about one item. Binary search learns about ten thousand items by examining one, because the sortedness lets a single comparison speak for an entire half. The information was purchased in advance, when the list was sorted, and binary search is how you collect.
Do one by hand, slowly. The sorted list:
2, 5, 8, 13, 21, 34, 55, 89
Target: 21. Keep two fingers on the list — one at each end — marking the region where the target could still be.
- The region is the whole list. The middle (with eight items, take the fourth) is 13. The target 21 is bigger, so everything from 13 leftward is dead. The region is now 21, 34, 55, 89.
- Middle of the region: 34. Too big; 34 and everything rightward is dead. The region is just 21.
- Check 21. Found, three comparisons.
Figure 1.1 — Binary search for 21: the region between the fingers halves at every comparison.
Now the same list, target 20 — a number that isn’t there. Run the same procedure: 13 (too small, go right), 34 (too big, go left), 21 (too big, go left) — and now the two fingers have crossed. The region where 20 could hide has shrunk to nothing. The procedure doesn’t just fail to find 20; it proves 20 absent, in three comparisons, where linear search would have needed eight. The expensive thing — certainty of absence — got cheap. That is what structure is for.
All 32 chapters of A First Taste of Algorithms · Foundations · All courses