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 2: Why Twenty Guesses Is Enough
Flip the question. Instead of asking how many guesses a million needs, ask how big a range a few guesses can handle. Start with one guess.
Add a second guess at the middle of three numbers. If it's wrong, the answer is higher or lower, which leaves one number for the last guess.
Three guesses: the middle one, plus a side of three on each end. Three plus three plus one is seven. Each guess uses the old range twice.
Count the guesses: one, three, seven, fifteen, thirty-one. Each count is double the one before, plus one. Those are all two raised to some power, minus one.
Each guess halves the range, so ten guesses reach about a thousand. Ten more doublings multiply that by a thousand, so twenty guesses cover 1,048,575 numbers.
Every guess you add doubles your reach, so a million numbers cost only twenty guesses, and a billion would cost just thirty.