Wall 2: Number Guessing Game (Binary Search)

Overall program description

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 think of and remember 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: 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:

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.

Examples

Let's say the user thinks of the number 14060. high is 10000 and low is 0. Here is the succession of guesses made by the algorithm:

Test Data

Guess: 2274
Output  Input
5000    lower
2500    lower
1250    higher
1875    higher
2187    higher
2343    lower
2265    higher
2304    lower
2284    lower
2274    yes
10                (guesses)

Guess: 7500
Output  Input
5000    higher
7500    yes
2                 (guesses)

Guess: 8325
Output  Input
5000    higher
7500    higher
8750    lower
8125    higher
8437    lower
8281    higher
8359    lower
8320    higher
8339    lower
8329    lower
8324    higher
8326    lower
8325    yes
13               (guesses)

Functions

You will define at least two functions in your program. The first -- named "myMain" -- everyone will have, and it is called with no arguments to make the whole program start execution. The second function you can design as you wish. Some suggestions are:

You can write more than two functions if you wish, but you need at least the myMain and one other.

You program will have this basic outline then:

   function myMain() {
      // in here goes the code for your main program
   
      // declare needed variables

      // tells the user to think of a number
      // then guesses that number by finding midpoint and getting the user
      // to say higher or lower
      // in here in the right places will be calls to your other function(s)
 
      return;
   }

   myMain(); // this call makes your main function run


   //-----------------------------------------------------------------------
   // define your second function... name it what you want, something 
   // descriptive of what it is defined to compute for you
   //-----------------------------------------------------------------------

   function mySecond( ... define appropriate args ... ) {
      // in here goes the code that will use the args to
      // compute what you have decided the function will do
      // like compute midpoint between high and low
      // or validate user input string
      // or whatever else you decide to write a function to do

      return something ;
   }

Hints

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.

Remember to divide and conquer. One strategy for this assignment is to write your function(s) first. Write a function that will check a string to see if it is valid as input... and test it. Write a function that will take two integers (hi and lo) and return the mid-point... and test it. Once you have a working function, or two, or three, you can begin writing your myMain function, in which you will be calling your smaller functions.