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 3: Why Sorting Makes Halving Possible
Halving a number range works because numbers have a built-in order. Now we ask: does the same trick work on an ordinary list?
Nine boxes are shuffled, and Chen is hidden somewhere among them. The middle box says Lopez, so Chen could be left or right. Since nothing is ruled out yet, nothing gets thrown away.
Same boxes, now alphabetical. Middle is Lopez. Chen comes before Lopez, so everything to the right is impossible. Four boxes gone with one look.
A dictionary works the same way. Open the middle, see earlier or later, ignore half the pages. Order is what makes the list say higher or lower.
So the speed of halving isn't magic in the search; it's paid for in advance by sorting. No order, no safe discarding, and no twenty guesses.