Binary Search Guessing Game

Combinatorics · Easy · Free problem

Your friend picks a number from

$ to $n$ and you have to find it. After each guess, your friend tells you whether the true number is higher, lower, or equal to your guess.

What is the minimum number of guesses $m$ that guarantees you can always identify the number, no matter what your friend picks? Give a formula for $m$ in terms of $n$, then compute the answer for $n = 8198$.

Hints

  1. Think about how much information each guess gives you -- after each response, how many candidates can you eliminate?
  2. With $m$ guesses you can distinguish at most
^m$ different numbers. Set ^m \geq n$ and solve for $m$.
  • The optimal strategy always guesses the midpoint of the remaining interval. The answer is $m = \lceil \log_2 n \rceil$.

    • Worked Solution

    How to Think About It: Each guess gives you one of three responses -- higher, lower, or correct -- but the useful information content is essentially one bit: you learn which half the number is in. With $m$ guesses you can distinguish at most ^m$ outcomes, so you need ^m \geq n$. This is a pure information-theoretic argument. There is no probability here, no estimation to do -- the answer is a ceiling of a logarithm and you should be able to state it in under 10 seconds.

    The optimal strategy is binary search: always guess the midpoint of the remaining interval. This guarantees you eliminate at least half the remaining candidates on every guess, regardless of what your friend says.

    Algorithm:

    1. Maintain an interval $[lo, hi]$, initially $[1, n]$.
    2. Guess $mid = \lfloor (lo + hi) / 2 \rfloor$.
    3. If the answer is "correct", done. If "higher", set $lo = mid + 1$. If "lower", set $hi = mid - 1$.
    4. Repeat until correct.

    Formal Solution:

    After each guess the remaining search space shrinks by (at least) a factor of 2. Starting with $n$ candidates, after $m$ guesses the worst-case remaining space is at most $\lceil n / 2^m \rceil$. We need this to reach 1:

    $2^m \geq n \implies m \geq \log_2 n$

    Since $m$ must be an integer, the minimum number of guesses is:

    $m = \lceil \log_2 n \rceil$

    Answer: For $n = 8198$:

    $\log_2(8198) = \log_2(8192) + \log_2(8198/8192) = 13 + \log_2(1.00073\ldots) \approx 13.001$

    Since ^{13} = 8192 < 8198 \leq 2^{14} = 16384$, we have $\lceil \log_2(8198) \rceil = 14$.

    The minimum guaranteed number of guesses is $m = \mathbf{14}$.

    Intuition

    This is a pure information-theoretic problem in disguise. Each guess with a higher/lower/correct response carries at most 1 bit of useful information (which half the number is in). With $m$ bits you can encode at most ^m$ distinct states, so $m = \lceil \log_2 n \rceil$ is a hard lower bound -- no strategy can do better, not even a randomized one. Binary search achieves this bound exactly, making it provably optimal.

    This same ceiling-of-log-base-2 formula shows up constantly in quant work: the depth of a balanced binary tree, the number of rounds in a tournament bracket, the entropy of a discrete uniform distribution, and the number of bits needed to represent a message from an alphabet of size $n$. Any time you are counting how many yes/no questions are needed to identify one item out of $n$, the answer is $\lceil \log_2 n \rceil$. The subtlety in this problem -- easily missed -- is that $n = 8198$ is just barely above ^{13} = 8192$, so you need 14 guesses, not 13. A good habit: always check whether $n$ is exactly a power of 2.

    Open the full interactive solver →