Guess Number Higher or Lower

easy binary search interactive

Problem

We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked.

Inputn = 10, hidden = 6

Output6

Guess 5 (low), 8 (high), 6 (correct).

hidden

def guess_number(n, guess):
    l, r = 1, n
    while l <= r:
        m = (l + r) // 2
        r2 = guess(m)
        if r2 == 0: return m
        if r2 < 0: r = m - 1
        else: l = m + 1
    return -1

function guessNumber(n, guess) {
  let l = 1, r = n;
  while (l <= r) {
    const m = (l + r) >> 1;
    const r2 = guess(m);
    if (r2 === 0) return m;
    if (r2 < 0) r = m - 1; else l = m + 1;
  }
  return -1;
}

class Solution {
    public int guessNumber(int n) {
        int l = 1, r = n;
        while (l <= r) {
            int m = (l + r) >>> 1;
            int r2 = guess(m);
            if (r2 == 0) return m;
            if (r2 < 0) r = m - 1; else l = m + 1;
        }
        return -1;
    }
}

int guessNumber(int n) {
    int l = 1, r = n;
    while (l <= r) {
        int m = (l + r) / 2;
        int r2 = guess(m);
        if (r2 == 0) return m;
        if (r2 < 0) r = m - 1; else l = m + 1;
    }
    return -1;
}

Explanation

This is the classic number-guessing game, and binary search is the optimal strategy: each guess at the middle of the range halves the possibilities, so we zero in fast.

We keep a window [l, r] over 1..n and guess the midpoint m. The oracle guess(m) returns 0 if we nailed it, a negative number if our guess was too high, and a positive number if it was too low.

On a 0 we return m immediately. If too high, the secret is smaller, so we move r = m - 1. If too low, it is larger, so l = m + 1. The window shrinks until we hit the number.

Example: n = 10, hidden 6. Guess 5 → too low, so l = 6. Guess 8 → too high, so r = 7. Guess 6 → correct, return 6.

Halving the range every guess makes this O(log n), far better than guessing one by one.

Time: O(log n) Space: O(1)