Nib asked for
Halving Step by Step
To search a sorted list, look at the middle item, and if it is not the target, throw away the half that cannot contain it and repeat on what remains until you find it or nothing is left.
5 steps, drawn by Nib. Read it here, or watch him draw it. Updated .
1fifteen names
Start with a sorted list, say 15 names in alphabetical order, and a name you are hunting for. Mark the whole list as your live region. Everything inside it is still a suspect; nothing has been ruled out yet.
Begin with the whole sorted list as your live region.
2look middle
Look at the item exactly in the middle, the eighth of fifteen. Compare it with your target. If it matches, you are done. This single look is the only information you buy each round, so you spend it where it is most useful: the center.
Check the middle item, and stop if it matches.
Why check the middle rather than the first item?
Show the answer
The middle splits the region evenly, so whichever way the answer goes, you discard as much as possible, about half.
3cross out half
If the middle item comes before your target alphabetically, then it and everything to its left are too early, because the list is sorted. Cross out that whole left half. If it comes after, cross out the right half instead. You eliminated about seven names by reading one.
Discard the half that cannot contain the target.
a common mix-upYou must scan the discarded half to be sure. You don't: sorted order guarantees the target cannot be there.
4repeat
Now repeat the same move on the smaller region: find its middle, compare, discard half. Seven items become three, then one. The list shrinks 15, 7, 3, 1, so at most four looks are needed, the same doubling from page 2 run in reverse.
Repeat on the remaining half; the region keeps shrinking.
If a list has 1,000,000 names, roughly how many looks at most?
Show the answer
About twenty, since each look halves the region and 2 to the 20th is about a million.
5two endings
The search ends one of two ways. Either a middle item matches and you report where it is, or the live region becomes empty, meaning every position has been ruled out. An empty region is a real answer: the target is not in the list.
Stop on a match, or when nothing is left, which means it's absent.
a common mix-upIf you don't find it, the method failed. An empty region is a correct, definite answer: not there.
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.