Assignment 2: Number Guessing Game (Binary Search)

You are to write a JavaScript program that plays a guessing game, like the one 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 number.

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
  user: lower
  high becomes 5000


• guess: floor((high+low))/2 is floor((5000+0)/2) is 2500
  user: lower
  high becomes 2500


• guess: floor((high+low))/2 is floor((2500+0)/2) is 1250
  user: higher
  low becomes 1250


• guess: floor((high+low))/2 is floor((2500+1250)/2) is 1875
  user: lower
  high becomes 1875


• guess: floor((high+low))/2 is floor((1875+1250)/2) is 1562
  user: lower
  high becomes 1562


• guess: floor((high+low))/2 is floor((1562+1250)/2) is 1406
  user: yes
  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 problem(s).

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.