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 4: Halving Step by Step
Here's a sorted list of fifteen names. The whole thing is still in play. Nothing's been ruled out. That's our live region.
Look only at the middle box, number eight. Compare it to what we're hunting. If it matches, we're done. One look, one question.
Middle comes before our target, so it and everything left of it are too early. Cross out that entire half. Seven names gone, one look.
Same move again on what's left. Fifteen, seven, three, one. Four looks at most. Those doublings from before, running backwards.
Two endings. A middle matches, and we've found it. Or the live region empties out, and that proves the name isn't in the list.
So the whole method is one move repeated: look at the middle, throw away the half that can't hold your answer, and keep going until you find it or run out. Next page: why that simple move is so easy to get wrong.