Two players are given a range of integers then each takes a turn to guess a number.
If the player guesses incorrectly it will be announced "Higher" or "Lower" and the other player takes their turn.
For a one player version of this game a binary search would be optimum. However in the two player version your opponent gets the information from your guess and can use it immediately. Is there a strategy that will work for this game?
Let $p_n$ be the probability that the first player can win this game starting with $n$ numbers, assuming both players play optimally. I will prove by induction that $$p_n=\begin{cases} \frac{1}{2} &\text{ if $n$ is even} \\ \frac{n+1}{2n} &\text{ if $n$ is odd.}\end{cases}$$
The base case $n=1$ is trivial: $p_1=1$, since the first player always wins.
Now suppose $n>1$ and we have proven the formula above for $p_k$ for all $k<n$, and now consider the game with $n$ numbers. First, suppose $n$ is odd. Since $p_k\geq 1/2$ for all $k<n$, if the first player doesn't guess correctly, the second player will have at least a $\frac{1}{2}$ chance of winning next. So the best thing the first player can do is ensure that if they are wrong, the remaining interval of numbers has an even number of numbers, so the second player has exactly a $\frac{1}{2}$ chance of winning. The first player can always do this by guessing either the largest or smallest possible number, since if they are wrong there will be $n-1$ numbers left. Using this strategy, the first player has a $\frac{1}{n}$ chance of winning immediately, and a $\frac{1}{2}$ chance of winning if they don't win immediately, giving $$p_n=\frac{1}{n}+\frac{1}{2}\cdot\frac{n-1}{n}=\frac{n+1}{2n}.$$
Now suppose $n$ is even. If the first player guesses the $k$th number in the range, they have a $\frac{1}{n}$ chance of winning immediately. If their guess is too high ($\frac{k-1}{n}$ chance), then they win with probability $1-p_{k-1}$. If their guess is too low ($\frac{n-k}{n}$ chance) they win with probability $1-p_{n-k}$. Of the numbers $k-1$ and $n-k$, one is even and the other is odd; let $a$ be the odd one so $n-a-1$ is the even one. Then the probability of the first player winning in this scenario is $$\frac{1}{n}+\frac{a}{n}(1-p_a)+\frac{n-a-1}{n}(1-p_{n-a-1})=\frac{1}{n}+\frac{a}{n}\cdot\frac{a-1}{2a}+\frac{n-a-1}{2n}=\frac{1}{2}.$$ This doesn't depend on $a$, so all choices of $k$ are equally good and $p_n=\frac{1}{2}$.
From the above proof we can also extract an optimal strategy. If $n$ is odd, you should pick either the highest or the lowest number (actually, any number which splits the range into two ranges of even lengths is equally good). If $n$ is even, it doesn't matter what number you pick.