After every time you guess, you're told if you're right, too high, or too low. Is there a strategy you can use to guarantee you'll get it on your 6th attempt (or lower)?
I know a strategy to get it on your 7th attempt.
Answer
Ask about 50.
If too high, then ask about 25.
If too low, then ask about 75.
Continue, continually halving the search-space. This requires $\lceil \log_2 (n+1)\rceil$ maximum questions. For 100, that's 7. It is a binary search algorithm known to be $\mathrm O(\log(n))$ time. I'm fairly sure there isn't a faster way. Binary search is considered the best for this problem - unless you are allowed to ask other questions.
No comments:
Post a Comment