Binary Search

An efficient algorithm for solving the guessing game is known as binary search. It takes advantage of the fact that the numbers between 1 and 100 are in order from lowest to highest. Given that fact, by guessing the midpoint of the range each time, you can effectively eliminate half the numbers in the list on each guess -- hence the name binary search.

For example, suppose we do the guessing game on the numbers 1 to 16.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16.

The optimal guess would be to guess the number at the midpoint of the range. Then after each guess you can effectively eliminate (approximately) half of the remaining numbers. For example, suppose the secret number is 13. Our first guess would be 8, which is too low. So we eliminate the bottom half of the range, leaving:

                       9, 10, 11, 12, 13, 14, 15, 16.

Our next guess would be 12, which is also too low, so we eliminate the bottom half of that range:

                                     13, 14, 15, 16.

Our next guess would be 14, which is too high, so we eliminate the top half of that range, giving:

Our final guess is 13, which is the secret number. So, in this case it took us 4 guesses to find the secret number.

The Binary Search Algorithm

Here's a pseudocode version of the binary search algorithm for the guessing game.

Repeat until your guess is correct or until you run out of numbers in the list.
    Guess that the target number is the middle number in the list.
    If the guess is too high,
       Cut off the top half of the list.
    If the guess is too low,
       Cut off the bottom half of the list.
    If the guess is correct,
       Stop.
If you ran out of numbers, the target number is not in the list.

How does that compare to the pseudocode that your team came up with?

Some Observations About Binary Search

Why does the algorithm need the clause "or until you run out of numbers"?
The reason is because for some binary searches the item being searched for doesn't occur in the list. For example, suppose we are searching for the misspelled word "algrism" in a list of English words. In that case the search will conclude that the word is not in the list.
For list of 16 items, you need a maximum of 4 guesses to find the secret number. For a list of 64 numbers you need a maximum of 6 guesses. Note that both of these numbers are powers of 2. So 16 is 2⁴ and 64 is 2⁶. In those cases the number of guesses is equal to the base 2 log of the number -- i.e., the base 2 logarithm of 16 is 4 and the base 2 logarithm of 64 is 6. (In more mathematical notation we would say log₂ 64 = 6..)
What about for any arbitrary number N? What's the maximum number of guesses in the general case? As you might guess, the answer is related to the base 2 log of N. But you have to be a little careful here. For example, the log₂ 100 = 6.6438. To figure out the maximum number of guesses in this case, we need to "round up" to 7 guesses.
Do you need a calculator to figure that out? Not really. Here's an easy way to figure out that maximum number of guesses for any value of N. Just write down the powers of 2 in a table like this:
```
X    2^X
==   ==
0    1
1    2
2    4
3    8
4   16
5   32
6   64
7  128
8  256
...
```
So, when N = 100, find the first number in the right column that's greater than or equal to 100 and the number in the left column will tell you how many guesses you need?
How many guesses would be needed to guess a secret number between 1 and 1000?