Computer Science

Question

You have a secret integer in a certain range in your mind. Write an efficient guess procedure from computer to get the target. For example, if the target is in [0, 100], then your algorithm should not take more than 7 tries.

After each guess, the following prompts are displayed:

How is the guess compared with your answer

 1. too big

 2. too small

 3. just right

Enter 1-3:

If the guess is too big, enter 1, if the guess is too small, enter 2, if the guess is just right, enter 3.

If you enter 1 or 2, which means the guess is too big or too small, the computer will make another guess based on your feedback.

Here is a sample run when the target is 17.

What is the possible smallest value: 0

What is the possible biggest value: 100

User, please pick an integer between 0 and 100.

Guess # 1: guess is 50

How is the guess compared with your answer

 1. too big

 2. too small

 3. just right

Enter 1-3: 1

Guess # 2: guess is 24

How is the guess compared with your answer

 1. too big

 2. too small

 3. just right

Enter 1-3: 1

Guess # 3: guess is 11

How is the guess compared with your answer

 1. too big

 2. too small

 3. just right

Enter 1-3: 2

Guess # 4: guess is 17

How is the guess compared with your answer

 1. too big

 2. too small

 3. just right

Enter 1-3: 3

Here is another run of the code when the target is 36.

What is the possible smallest value: 0

What is the possible biggest value: 100

User, please pick an integer between 0 and 100.

Guess # 1: guess is 50

How is the guess compared with your answer

 1. too big

 2. too small

 3. just right

Enter 1-3: 1

Guess # 2: guess is 24

How is the guess compared with your answer

 1. too big

 2. too small

 3. just right

Enter 1-3: 2

Guess # 3: guess is 37

How is the guess compared with your answer

 1. too big

 2. too small

 3. just right

Enter 1-3: 1

Guess # 4: guess is 30

How is the guess compared with your answer

 1. too big

 2. too small

 3. just right

Enter 1-3: 2

Guess # 5: guess is 33

How is the guess compared with your answer

 1. too big

 2. too small

 3. just right

Enter 1-3: 2

Guess # 6: guess is 35

How is the guess compared with your answer

 1. too big

2. too small

 3. just right

Enter 1-3: 2

Guess # 7: the answer must be 36

Question:

When the target is an integer in [0, 1000], what is the maximum number of guesses your program will take? Give an example of one such target.

What is the maximum number of guesses if the target is an integer in [800, 1000]? Give an example of one such target.

Write the answer in the comments.

Answer 1

The most efficient algorithm would be to guess the average between the current lower and upper bounds. So, in the case of a range 0-1000, the first guess would be 500. If too high, next would be 250; too low, next is 750. Each guess if wrong would eliminate half of the remaining possibilities. So, worst case scenario, if the target was 2, the successive guesses would be 500, 250, 125, 62, 31, 15, 7, 3, 1, 2