What is the minimum number of guesses needed to find a specific number if you are given the hint higher or lower for each guess you make?

Answer 1

Assuming that you want to discount luck (if not, the answer would be 1), and that the guesser always guesses the median of the remaining range, the answer would be the (ceiling of the log(base 2) of the count of numbers in the range). If the log(base 2) is an exact integer, add 1.

Example 1, pick a number between 1 and 9. There are 9 numbers in the range, so the log(base2) of 9 is ~3.16. The ceiling of that is 4. Do not add 1 for a final answer of 4.

The full range is 1,2,3,4,5,6,7,8,9. The median is 5

First guess is 5. Higher - 6,7,8,9 is remaining range. 7 and 8 are the median numbers

Second Guess is 8. Lower - 6,7 is the remaining range. 6 and 7 are the median numbers.

Third guess is 7. Lower - 6 is the remaining range. 6 is the median number

Fourth guess is 6. Correct.

Example 2, pick a number between 1 and 16. There are 16 numbers in the range, so the log(base 2) of 16 is 4. The ceiling of 4 is 4. Add the 1 because the Log(base 2) is an integer, for a final answer of 5.

Full range is 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16. The median numbers are 8 and 9.

First Guess is 9. Lower - 1,2,3,4,5,6,7,8 is the remaining range. 4 and 5 are the median numbers

Second Guess is 4. Higher - 5,6,7,8 is the remaining range. 6 and 7 are the median numbers.

Third Guess is 6. Higher - 7,8 is the remaining range. 7 and 8 are the median numbers.

Fourth Guess is 7. Higher - 8 is the remaining range. 8 is the median.

Fifth guess is 8. Correct

Both of these examples show worst case scenarios. A "lucky guess" will reduce the number of guess needed, possibly all the way to 1.

Note: I do realize that to a math purist, in the examples where I said that the median numbers were x and y, the correct answer is that the median number is between x and y. Since I can not guess the number between the two numbers, I am bending the definition of median to treat the two bordering numbers as the median when the strict definition would list the median as being between those two numbers.