[alThor]

This is an interesting question. Binary search minimizes average search time, but in a 2-player game like this, one should be more concerned with median type statistics than EV type stats. It is evident that the players should not follow a binary search always.

Consider a version of this game where you both have to guess a random integer 1,2,3,4. (To simplify, suppose your integers are independent, so that it is possible that you both have to guess the same integer.)

If player one uses a binary search, he first asks "Higher or lower than 2.5?" Then he will guess specific integers after that, and will find the right integer in either two or three guesses, with 50-50 probability.

If player two plkays this strategy, he will also get the right answer in two or three guesses, with 50-50 probability. But since he moves second, he wins with only 25% probability.

So suppose instead player 2 simply guesses an integer right away! That already gives him a 25% chance of winning if player 1 uses binary. But in addition, if he's wrong and player 1 fails to get the answer on guess #2, player 2 has an additional 33% shot at winning on his second guess, for an overall probability of 25% + (.75)(.5)(33%) = 3/8.

The optimal strategy in this game will be complicated by the fact that, with more integers, when an opponent makes an aggressive move, your response is dependent on whether he succeeded in narrowing the field a lot.

alThor