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

Nib asked for

Why Sorting Makes Halving Possible

the short answer

Halving only works on a list arranged in order, because only then does checking one middle item tell you that everything on one whole side is too small or too large.

4 steps, drawn by Nib. Read it here, or watch him draw it. Updated 16 Oct 2026.

1built-in order

Last page showed that twenty halvings cover a million possibilities. That worked for a hidden number because numbers come pre-arranged: if 500,000 is too low, every number below it is too low as well. Now swap the hidden number for something stored in a list, and ask whether the same trick still works.

Halving needs a reason to throw away a whole side.

2shuffled boxes

Picture nine shuffled boxes with names on them: Moore, Adams, Young, Chen, Lopez, Singh, Baker, Patel, Davis. You want Chen. You open the middle box and find Lopez. Does that tell you anything about where Chen is? No. Chen could be among the four boxes to the left or the four to the right, so you cannot discard either side.

In a shuffled list, one peek tells you nothing about the rest.

3sorted boxes

Now line the same boxes up alphabetically: Adams, Baker, Chen, Davis, Lopez, Moore, Patel, Singh, Young. The middle box is still Lopez, but it now says a great deal. Chen comes before Lopez in the alphabet, so Chen cannot be in any box to the right. Those four boxes vanish from your search in one stroke.

In an ordered list, one peek rules out an entire side.

4no order vs order

This is exactly why a phone book or dictionary lets you find a name quickly: you open it near the middle, see whether your word comes earlier or later, and ignore a huge block of pages. The order is what turns each peek into a verdict about a whole region, just like 'higher' or 'lower' did in the guessing game. The list itself plays the role of the person answering you.

Order makes the list answer 'higher or lower' for you.

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.