In the "guess-my-number" game, one player (player A) makes guesses at another player's (player B) secret number. All games would follow the following procedure:
Player B decides on a number between a known, set limit (for example, he/she may only choose a number between 1 and 100), this will become the player's "secret number" (the secret number must be an integer)
Player A then guesses an initial number
Player B responds by (honestly) declaring Player A's response to be either too high, too low, or correct
The process repeats, Player A guesses a number based on previous feedback, and Player B responds, until Player A guesses correctly
Anyways, I've heard that the most efficient method for Player A to guess player B's number would be the binary search, as it takes logarithmic time. First of all, I want to confirm that this is true, but I have another part to my question...
What if the game was modified so that Player B lied on occasion, under the following, known circumstances:
Player B only lies one-third of the time
Player B does not lie twice in a row
Player B only lies when the guess is too high, if the guess is too low or correct, Player B will not lie
- When Player B lies, the lie is guaranteed to be that the guess is too low
Would it still be most efficient to perform a binary search, and if so, how would I modify it to fit this situation more precisely? Alternatively, what other algorithm would be most efficient?
edit: related: Twenty questions against a liar