You are trying to guess my favorite number. I tell you it is from 1-100 somewhere and is an interger. You can guess anything you like and I will tell you whether my number is higher or lower then your guess. What is the smallest number of guesses you can make to make sure you will get my number, no matter what it is?
Assume that I don't lie to you about the greater or less than value.
This is a standard case for a binary search
. Each successive guess is at the half-way mark (or the closest to it) of the range that is still 'in play'.
e.g. at the start the entire range 1-100 is 'in play'. You guess 50 and lets say you are told that the number is higher than 50. Now, the range 1-50 is ruled out and the range 51-100 is still 'in play'. And so on...
The minimum number of guesses within which you are sure to guess the number correctly is 7.
Posted by Sanjay
on 2003-06-16 09:46:30