Assignment 2: Number Guessing Game (Binary Search)
Overall program description
we played in class.
First the program will ask the user to think of an integer between 0 and
10,000. There is no input here, just a message to the user to select a
The program will then guess the number using
the binary search procedure
we discussed in class.
At all times your program will maintain two
variables... let's call them "high" and "low".
At all times, high and low will tell the upper and lower
integers of the range in which the program has decided the
user's number must lie. Obviously in the beginning, the user's
number must be between 0 and 10000, so you will start "high" with
the value 10000 and "low" with the value 0.
Now we begin making guesses. The program will do this in a loop,
and the loop will end when the number is correctly guessed.
Inside the loop, the program will first make a guess. This is
done by finding the midpoint in the range between "high" and "low".
The midpoint is defined this way:
Math.floor ( ( high + low ) / 2 )
So you compute this midpoint and ask the user if the guess is correct.
The user will reply "higher", "lower", or "yes" depending on how the guess
relates to the real number:
If the guess is too low, the user types "higher".
If the guess is too high, the user types "lower".
If the guess is spot on, the user types "yes" and the guessing loop will end.
Then based on the user's reply, the program will respond in one of three ways.
If the guess is too low, before going back to the beginning of the loop to
make another guess, you first move the variable "low" up to the guess.
This is because if the guess is too low, all numbers below that guess are too
low as well and we can toss them... that is, make sure we don't guess them.
If the guess is too high, we move the variable "high" down to the guess.
If the reply is "yes" we nailed it and we stop the program.
Keep track of how many guess are made; when the number is guessed,
tell the user how many guesses the program made.
Let's say the user thinks of the number 1406.
high is 10000 and low is 0.
Here is the succession of guesses made by the algorithm:
- guess: floor((high+low))/2 is floor((10000+0)/2) is 5000
high becomes 5000
- guess: floor((high+low))/2 is floor((5000+0)/2) is 2500
high becomes 2500
- guess: floor((high+low))/2 is floor((2500+0)/2) is 1250
low becomes 1250
- guess: floor((high+low))/2 is floor((2500+1250)/2) is 1875
high becomes 1875
- guess: floor((high+low))/2 is floor((1875+1250)/2) is 1562
high becomes 1562
- guess: floor((high+low))/2 is floor((1562+1250)/2) is 1406
guessing loop ends
We took 6 guesses.
To keep track of how many guesses are made, use a counter.
Remember to validate user input where needed.
Grow your program a little piece at a time. Do not type in 100
lines of code and then hope it works. It won't... and then you
won't be able to easily find the line(s) that are causing the
Instead, build an outline of the algorithm with comments.
Then go back and convert each comment into a few lines of code.
Then test the few lines you added, see if the program is doing
what you expect it to be doing.
Lather, rinse, repeat.