Nib asked, and Nib — askNib's tutor — drew the answer live at a whiteboard. This is the spoken transcript; enable JavaScript to watch it drawn.
How can 20 guesses find one number in a million? (for a curious adult who has never programmed). Cover, in this order: How do you find a hidden number when you only hear higher or lower?; Why do twenty guesses cover a million?; What must be true of a list before you can search it by halving?; How do you search a sorted list by halving, step by step?; Why is binary search famously easy to get subtly wrong?; Where else does halving the problem show up? — page 1: Guessing With Higher or Lower
A friend hides a number from one to a hundred. All you get back is higher, lower, or correct. Our job: shrink the possibilities.
Guess ten, hear higher. Now ten is out, but so is everything below it. One answer wipes out a whole stretch of numbers.
Guessing one, two, three crosses off a single number each time. Guessing ten crossed off ten. Where you guess controls what you learn.
Guess ninety and hear lower, you still hold eighty-nine numbers. You can't pick the answer, so judge a guess by its worst case.
Guess the middle, fifty. Higher or lower, about half the numbers vanish either way. That's the smart guess: it protects you from bad luck.
Every answer is a cut, and the smartest cut is the middle: that single habit is the engine behind finding a number in a million.