Higher/Lower guessing game with no upper bound 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?

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.