Find the number using binary search against one possible lie

We all know this classic problem, "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess.

But what if the interactor may lie to us in one case? For example, the number is $3$ and the maximum number we can guess is $10$, but when we ask whether it is greater than $5$ and it replies yes and for the rest of queries it answers correctly. A simple binary search would fail.

How to proceed in this case? What is the minimum number of query in the worst case?

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey.

In your particular case, the problem can be easily solved without any asymptotic change in the computational complexity. Run the binary search three times. At least two of the three results must be equal to the hidden number. Return the majority result.

There are other elegant ways to handle up to $k$ of lies by only using $O(\log n + k)$ time (where $k$ might be a function of $n$).

StackExchange Computer Science Q#126782, answer score: 9