You are playing a game on a machine. First of all the machine chooses a number N. You do not know this number and you need to make guesses to find it. Suppose you choose the number k, the machine tells whether k is less than, equal to or greater than N. The game ends if k is equal to N. If you guess a number which is greater than N, then it is considered a bad guess. You cannot make more than 1 bad guess.

Expected time complexity is sqrt(n) time. I find it impossible to do, when only one bad guess is allowed. Any help would be appreciated.