Write a program that asks the user to think of an integer between 1 and 1,000,000, and then guesses the number through a series of yes/no questions. To guess the number, the program calls a recursive method guess that has two parameters, low and high. The precondition for the method requires that the user’s number lie in the range low...high so that the program’s initial call is to guess(1, 1000000). What is a good stopping case for guess, when it can guess the user’s number with little or no work? Answer: If (low == high), then there is only one possible number, and the method can guess that number. On the other hand, if (low < high), then the method should calculate a point near the middle of the range:

midpoint = (low + high) / 2;

Then the method asks the user whether the midpoint is the correct number. If so, the method is finished. On the other hand, if the midpoint is not the user’s number, then the method asks whether the correct number is larger than midpoint. If so, the method knows that the user’s number lies in the range midpoint + 1 to high, and a recursive call can be made to solve the smaller problem of finding a user’s number in the range midpoint + 1 to high. On the other hand, if the user’s number is not larger than midpoint, then a recursive call can be made to solve the smaller problem of finding a user’s number in the range low to midpoint - 1. This method of searching is called binary search, which we will explore further in Chapter 11.