Number guessing game with a twist

Question

Normally, a number guessing game algorithm, given some secret number, would just be a modification of the binary search algorithm if it is known if the guess is larger or smaller than the secret number. Say the secret number was 13. An algorithm would try 1(smaller than 13), 2(smaller than 13), 4(smaller than 13), 8(smaller than 13), 16(larger than 13, backtrack), 10(smaller than 13), 13(equal to secret, stop.)

However, what if it wasn't known whether the guess is smaller or larger than the secret number, and the only status is equal or not equal? What algorithm would be the most efficient? Certainly not brute forcing...

EDIT: For both situations, there's an upper and lower bound as to what the number could be.

Answer 1

If you imagine an adversary who doesn't actually make their mind up about the number until they have to then you can see that you might have to ask for every number in turn. They can simply say "wrong answer" until you have guessed every possible number, and their answers could have been genuine, based on an initial choice of whatever the last number you guessed was.

Answer 2

I am not really sure the kind of performance gains you expect for such a problem. As suggested by most there is no significant way to improve the worst case from O(n). You could also still stick with the binary search approach where in every unequal guess is initially considered as a less than operation '<' and once this list gets exhausted you can consider every unequal guess as a greater than operation >. In practical scenarios when playing 'guess the number game' I believe this "may" be better than brute force sequentially.

Generally if we can find an algorithm for guessing the number in minimum guesses with certainty, I am sure many games played around the world will soon be redundant :)

Answer 3

If equal/not equal is the only information you get, then there is no algorithm that will give you better average case or better worst case performance than brute force (I.e starting from the lower bound and working up to the upper bound).

To get even slightly better average case performance, you would need some kind of additional information. At least something statistical like 'only 10% of the secret numbers are ever below 20', etc, which could then be used to elicit better average case performance (in this example, maybe by starting the search at 21).

Even then, worst case performance would still be no better than brute force.

Answer 4

Well, the information you have is that the answer is not correct. Since it is the only information available, I would assume brute force would be the only approach. You could as well just start from zero and go up.