The halving game, and what a logarithm is

Why throwing away half of what is left at each step makes even enormous collections small, and what that is worth when sorting.

Someone thinks of a whole number between 1 and 100 and you have to guess it. After each guess you are told only whether the true number is higher or lower. How many guesses do you need?

Guessing 1, then 2, then 3 could take a hundred guesses. The good strategy is to guess the middle every time, because whichever answer you get, half of the remaining possibilities disappear. Let us actually play it, with the secret number being 73.

Six guesses, and seven is enough to guarantee finding any number from 1 to 100 whatever it is. That is the whole idea, and now comes the part that matters.

Doubling the problem costs one more guess

Suppose the range is 1 to 200 instead. Your first guess splits it into two halves of 100, and you are back to the problem you already know how to solve in seven. So 200 needs eight. By the same argument 400 needs nine, and 800 needs ten.

Keep going and the numbers stop feeling reasonable, in a good way.

A billion possibilities, thirty guesses. Not thirty thousand, not thirty million. Thirty. And going from a billion to two billion costs you exactly one more guess.

The name for that count

The number in the right-hand column has a name. It is the logarithm of n, and specifically the logarithm in base two, because we are halving. If the word is unfamiliar or unwelcome, replace it in your head with a plain question, because that is genuinely all it means here:

The same question read backwards is: how many times must you double 1 before you reach n? Doubling from 1 goes 1, 2, 4, 8, 16, 32, 64, 128, and that is seven doublings to pass 100. Which is exactly the seven guesses we needed. Halving down and doubling up are the same staircase seen from opposite ends.

Where this shows up

Anywhere you can rule out half of what remains in one step. Looking up a word in a paper dictionary works this way: you open it near the middle, see whether your word is before or after, and never look at the other half again.

It also works on a collection of items kept in increasing order, and that case is worth doing in full rather than asserting, because it is the one you will meet most. Here are eight numbers in order, with the index numbers from earlier in the section written above each one.

index:      0       1       2       3       4       5       6       7
         [  3  ] [  8  ] [ 12  ] [ 19  ] [ 26  ] [ 33  ] [ 41  ] [ 57  ]

We are looking for 41, and we do not know where it is. The guessing game says to go to the middle, so we look at index 3.

Three checks for eight numbers. That is the first row of the halving table earlier in this lesson, where a range of 8 needed 3 guesses, and it is the same behaviour for the same reason: every check throws away half of what was still in play. Checking one at a time from the left would have taken seven. Searching a well-shaped tree, later in the course, works this way too, and the version for a sorted run gets a lesson of its own in the section on arrays.

The pattern that was waiting for this number

The last lesson left a fifth growth pattern unfinished, because counting it needed the halving count and you did not have it yet. Now you do, so we can finish the job. This is the pattern that good methods for putting things into order land on, and it sits between growing in step with the data and growing with the square.

Say you have a thousand cards to put into order. One way is to compare every card with every other card, which is the handshake pattern from the last lesson: about a million comparisons. A better way is to split the pile in half, put each half in order the same way, and then merge the two ordered halves by repeatedly taking whichever of the two top cards is smaller.

Count what that costs, in two parts. First, how many rounds there are. Splitting a thousand cards into two piles of five hundred, then four piles of two hundred and fifty, and so on until every pile is a single card, is exactly halving a thousand down to one. That is the count you just worked out: about ten rounds. Putting the piles back together takes the same number of rounds as taking them apart did, so there are about ten merging rounds as well.

Second, what one merging round costs. In each round every one of the thousand cards is picked up exactly once as the piles are joined back up, so a round costs about a thousand steps. About ten rounds at about a thousand steps each is about 10,000 steps, against the million that comparing every pair would have needed. The saving comes from the work being the number of items multiplied by the halving count, rather than by itself.

In the table of patterns from the last lesson, this one belongs between the last two columns and far nearer the left-hand one. At a thousand items it is about 10,000 steps, where growing in step is 1,000 and growing with the square is a million.