$\begingroup$

In the classic game my opponent selects a number from a range and then I guess and she tells me "Higher" or "Lower" until I guess correctly. This can simply be solved using a binary search.

However if my opponent states that they have selected a natural number is there any any strategy I can employ to minimise the number of guesses I have to make?

$\endgroup$

1 Answer

$\begingroup$

Start with an arbitrary guess and double it until your opponent says "Lower". Now you have an upper bound and you can do the binary search that you are familiar with.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy