Algorithms in a Nutshell

(^24) | Chapter 2: The Mathematics of Algorithms
In each turn, depending upon the specific answers from the bartender, the size of
the potential range containing the hidden number is cut in about half each time.
Eventually, the range of the hidden number will be limited to just one possible
number; this happens after⎡log (n)⎤turns. The ceiling function⎡x⎤rounds the
numberxup to the smallest integer greater than or equal tox. For example, if the
bartender chooses a number between 1 and 10, you could guess it in⎡log (10)⎤=
⎡3.32⎤, or four guesses, as shown in the table.
This same approach works equally well for 1,000,000 numbers. In fact, the
GUESSINGalgorithm shown in Example 2-1 works for any range [low,high] and
determines the value ofnin⎡log (high–low+ 1 )⎤turns. If there are 1,000,000
numbers, this algorithm will locate the number in at most⎡log (1,000,000)⎤=
⎡19.93⎤, or 20 guesses (the worst case).
3 Is it 5?
TOO HIGH
Is it 2?
TOO LOW
Is it 3?
YOU WIN
4 Is it 5?
TOO HIGH
Is it 2?
TOO LOW
Is it 3?
TOO LOW, so it must be 4
5 Is it 5?
YOU WIN
6 Is it 5?
TOO LOW
Is it 8?
TOO HIGH
Is it 6?
YOU WIN
7 Is it 5?
TOO LOW
Is it 8?
TOO HIGH
Is it 6?
TOO LOW, so it must be 7
8 Is it 5?
TOO LOW
Is it 8?
YOU WIN
9 Is it 5?
TOO LOW
Is it 8?
TOO LOW
Is it 9?
YOU WIN
10 Is it 5?
TOO LOW
Is it 8?
TOO LOW
Is it 9?
TOO LOW, so it must be 10
Example 2-1. Java code to guess number in range [low,high]
// Compute number of turns when n is guaranteed to be in range [low,high].
public static int turns(int n, int low, int high) {
int turns = 0;
// While more than two potential numbers remain to be checked, continue.
while (high – low≤2) {
// Prepare midpoint of [low,high] as the guess.
turns++;
int mid = (low + high)/2;
if (mid == n) {
return turns;
} else if (mid < n) {
low = mid + 1;
} else {
high = mid - 1;
Table 2-1. Sample behavior for guessing number from 1–10 (continued)
Number First guess Second guess Third guess
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use