Lessons · Searching
Searching: find it in as few looks as you can
Each box hides a number. Opening a box is the only way to see inside, so a good search opens as few as possible. That is how your phone finds one contact among thousands.
Try it offline ·
- You need
- Time
Think about it
Count your looks
Make a tally mark every time you look at a card or make a guess. Who needed the fewest?
Prints just this card, on one page.
Why halving wins
Every time binary search opens a box, half of what is left disappears. Doubling the number of boxes adds only one more look.
| Boxes | Linear search, at most | Binary search, at most |
|---|---|---|
| 15 | 15 | 4 |
| 100 | 100 | 7 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
| 8,000,000,000 (everyone on Earth) | 8,000,000,000 | 33 |
The catch: binary search only works when things are already in order. That is one reason computers spend so much effort sorting.