Alice has a hidden random integer $a$ in range $[1, 2^n]$. Each time, Bob can guess a number $x$, and Alice will answer whether $x \ge a$ or $x < a$. However, Alice can give a wrong answer for at most 1 times. In the worst case, how many guesses does Bob need to surely find out $a$?
The best result I could get is about $n + 2\sqrt{n}$. Are there any better solutions?
Thanks for the comments! It seems that I can't mark a comment as answer, so I have to post one.
This problem has been solved previously.
If one can ask a general yes-no question (whether or not $a \in S$), the answer is the smallest integer k that satisfies $2^{k-n} \ge k+1$. Therefore, $k \approx n + \log_2{n}$. The proof can be found here.
This paper shows that when only comparisons are allowed, the answer $k' \le k+1$. However, I haven't found out how to obtain an exact answer.