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:

Our next guess would be 12, which is also too low, so we eliminate the bottom half of that range:9, 10, 11, 12, 13, 14, 15, 16.

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

13

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

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?

- 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
^{4}and 64 is 2^{6}. 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*.)_{2}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*To figure out the maximum number of guesses in this case, we need to "round up" to 7 guesses._{2}100 = 6.6438.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?