Guess the Hidden Number

easy binary search interactive

Problem

Pick a hidden integer between 1 and n. An oracle guess(x) answers: 0 if correct, -1 if too high, +1 if too low. Find the hidden number with the minimum number of guesses by bisecting the range.

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;
}

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