Number Guessing Game Binary Search

Let's look at the guessing game as another example of using a Divide and Conquer Algorithm by halving our possible number of guesses. To play the guessing game, a person (player A) will choose a random number from n to m, another person (player B) will have to guess player A's number in "x" turns. Player A will assist player B by telling player B if the number they guessed is higher than or lower than player A's randomly chosen number. The Algorithm will tell you if it is possible to guess player A's number in the given amount of turns x, and will tell the maximum amount of tries or guesses you will need in order to guess there number correctly. The Number Guessing Game uses binary search to quickly find a solution. A binary search is a dichotomic divide and conquer search algorithm. The maximum number of turns it takes to guess a number from 1 to 100 is log₂(100 -1 +1)= log₂(100) = 7. Hence the worst case running time is log₂(Max - Min + 1).

log₂(N) → O(log N)

Example:

An example of how the game works:
Player A: I am thinking of a number from 1 to 100, can you guess my number within 7 turns ?
Player B: Sure, is your number 89 ?
Player A: Nope guess a lower number.
Player B: Okay, is your number 75 ?
Player A: Nope, guess a higher number.
Player B: Okay is your number 80 ?
Player A: Nope, guess a higher number.
Player B: Okay, is your number 88 ?
Player A: Yes, congratulations you guessed my number in 4 turns you win!

Code:Guessing Game

/* This is the number guessing game program */
/* This program was written in the C programing language 
    By  randerson112358
*/

# include <stdio.h>
# include <stdlib.h>
# include <math.h>   // Library used for math in this case log() and ciel()

int main(void)
{
	//Declaring Variables to be used
	int lowRange = 1;
	int highRange = 100;
	int possibleGuesses = highRange + lowRange - 1;
	int maxTurns = (int)(log(possibleGuesses)/log(2)) + 1; // = log base 2 of possible guesses by rules of logarithms
	int yourGuess;
	int playerAnswer;
	int countNumTurns = 1;

	printf("Choose a number from %d to %d.\n", lowRange, highRange);
	printf("I will guess your number in %d turns or less.\n\n", maxTurns );

			//This loops through the algorithm
			do{
				possibleGuesses = highRange + lowRange - 1;
				yourGuess = (int) ceil(possibleGuesses / 2.0);

				printf("Is your number %d ?\n",yourGuess );
				printf("Press (1) Yes (2) Guess a lower number (3) Guess a higher number\n");
                                scanf("%d", &playerAnswer);

				if(playerAnswer == 3)//Guess was too low
					lowRange = yourGuess + 1;
				if(playerAnswer == 2) // Guess was too high
					highRange = yourGuess - 1;
				if (playerAnswer == 1)
				    break;
                               
                                 countNumTurns++;
                                
			}while(playerAnswer != 1 && countNumTurns <=maxTurns);

	//Print the end results
        if(countNumTurns > maxTurns)
    	     printf("You made a mistake somewhere, you've exceeded the maximum turns. \n");
	else
	     printf("I guessed your number in %d turns !\n", countNumTurns );

	system("pause"); //This is only for windows operating system otherwise comment it out.
}

Try the guessing game below, it will always guess your number within 7 turns

The algorithm used to make this game, uses a divide and conquer approach by halving the possible choices/guesses !

Instructions to play:

1) Think of a number in your head from 1 to 100

2) The program will start off by guessing if your number is 50

3) You must tell the program if it's guess was lower or higher than the number you thought of in your head in step 1, if it guessed it right click correct

4) If the computer didn't guess your number continue with steps 2 - 4, else go to step 5

5) The program should have guessed your number within 7 turns. Click Refresh to play again