Thinking Recursively with Java

2.2. Computational Complexity

Many years ago, before the advent of the video arcade and the home computer, computer games were a relatively rare treat to be found at the local science or children's museum. One of the most widely circulated was a simple Guess-the- Number game, played as follows:

The game continued in this fashion, accepting new guesses, until the player discovered the computer's secret number.

For children who were happy to spend a little extra time with one of these games, twelve guesses hardly seemed excessive. Eventually, however, even relatively young players would discover that they could do better by exploiting a more systematic strategy.

In developing such a strategy, the central idea is that each guess must narrow the range to be searched as quickly as possible, which can be accomplished by choosing the value closest to the middle of the available range. For example, the original problem can be expressed in English as

Guess a number in the range 1 to 100.

If you guess 50 and discover that it is too large, you can reduce the original problem to this somewhat more restricted one:

Guess a number in the range 1 to 49.

This refinement has the effect of reducing the original problem to an identical subproblem in which the number is limited to a more restricted ...