Stuck on a java assignment, binary search algorithm

Question

I have hit this point on an assignment and I was hoping for some guidance. Basically the program is supposed to have a user think of a number between 1-100 and then ask if it is higher or lower than 50. Then the program outputs the midpoint until of the range until the answer is correct. For example if 'h' was entered it would then ask if the number is 75, if the response is then 'l' it would ask if the number is 67, etc.

I think I have built the framework but I am really struggling with how to approach the next step in finding the midpoint. Any guidance would be greatly appreciated.

import java.util.Scanner;

public class numberguess 
{

    public static void main(String[] args) 
    {    
        String shouldPlayAgain = "y";
        String response = "h";

        Scanner keyboard = new Scanner(System.in);

        do
            {
                System.out.println("Guess a number between 1 and 100.");
                System.out.print("Is it 50? (h/l/c): ");
                response = keyboard.nextLine();

                    if (response.equals("h"))
                        {
                            System.out.println("Is it 75? (h/l/c): ");
                        }

                    if (response.equals("l"))
                        {
                            System.out.println("Is it 25? (h/l/c): ");
                        }

                System.out.print("Great! Do you want to play again? (y/n): ");
                shouldPlayAgain = keyboard.nextLine();
            }
        while (shouldPlayAgain.equals("y"));
        }
}

Please refer algs4.cs.princeton.edu/11model/BinarySearch.java.html Hope it will be helpful — The PowerHouse
– The PowerHouse, Commented Sep 10, 2013 at 5:11

Kon · Accepted Answer · 2013-09-10 05:16:42Z

2

I'm not going to write the solution out, but I'll try to point you in the right direction. Hopefully that'll get you going and on the right track to implement the solution yourself. Feel free to ask specific questions if anything is unclear.

You need to create two variables to keep track of your lower and upper bounds for guessing.

int lowerBound = 0;
int upperBound = 100;

Then you iteratively guess the middle, which is:

(upperBound + lowerBound) / 2;

Let's say you guess 50. Then the user enters H. This means that the number is bigger than 50, but less than 100. So now you know that your new lower bound is 50, set:

lowerBound = 50;

And repeat the process, this time (upperBound + lowerBound) / 2; gives you 75, and so on. You know you're done guessing if lowerBound equals upperBound. All that remains is to structure this process in a loop, and you're done.

edited Sep 10, 2013 at 5:16

answered Sep 10, 2013 at 5:11

Kon

10.8k6 gold badges46 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Peter Lawrey Over a year ago

Technically you want (lowerBound + upperBound) >>> 1 if you want positive numbers and want to avoid overflows

Community · Accepted Answer · 2020-06-20 09:12:55Z

include

using namespace std;

//function prototypes

void playOneGame();

void getUserResponseToGuess(int guess, char& result);

int getMidPoint(int low, int high);

//main method

int main()

{

 //declare variables

 char response;

 //promt the users choice

 cout << "Ready to play (y/n)? ";

 cin >> response;

 //reapeat the loop until the user'c choice is no

 while (response == 'y')

 {

      //Call the function initially

      playOneGame();

      cout<<"Great! Do you want to play again (y/n)? ";

      cin >> response;

 }

 cout << "Thanks for playing!" << endl;

 system("pause");

 return 0;

}

//implement the function playOneGame

void playOneGame()

{

 //initialGuess

 int guess = 50;       // initial guess

 int low = 1;       // initial low point

 int high = 100;       // initial high point

 char result;

 cout<< "Think of a number between 1 to 100. " << endl;

//call the function to guess the users number //through binary search

 getUserResponseToGuess(guess, result);

 //Repeat the loop, until the answer is correct

 while (result != 'c')

 {

      //If the answer is high

      if (result == 'h')

      {

          low = guess;

          //compute the midpoint

          guess = getMidPoint(low, high);

          //call the function

          getUserResponseToGuess(guess, result);

      }

      else

      {

          high = guess;

          guess = getMidPoint(low, high);

          getUserResponseToGuess(guess, result);

      }

 }

}

//This function inputs the computer guess and displays it //to the user.

void getUserResponseToGuess(int guess, char& result)

{

 cout << "Is it " << guess << " (h/l/c)?"<< endl;

 cin >> result;

}

//This function inputs the low and high and it returns //the midpoint between them.

int getMidPoint(int low, int high)

{

 return (low + high) / 2;

}

Collectives™ on Stack Overflow

Stuck on a java assignment, binary search algorithm

2 Answers 2

1 Comment

include

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

include

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related