#374 - Guess Number Higher or Lower

EasyBinary Search

We are playing a guessing game. I picked a number from 1 to n. You call guess(num) which returns -1 (my number is lower), 1 (my number is higher), or 0 (correct). Return the number I picked.

Input	Output
n = 10, pick = 6	6
n = 1, pick = 1	1
n = 2, pick = 1	1

Solution Space

Try it

/**
 * Finds the picked number in [1, n] using the guess API.
 * guess(num) returns -1 if pick < num, 1 if pick > num, 0 if correct.
 *
 * @param n Upper bound of the range
 * @returns The picked number
 */
export function guessNumber(n: number): number {
  let lo = 1;
  let hi = n;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    const result = guess(mid);

    if (result === 0) return mid;
    if (result === -1)
      hi = mid - 1; // pick is lower
    else lo = mid + 1; // pick is higher
  }

  return -1; // unreachable
}

Approach: binary search – classic halving of the search space using the `guess` API feedback.

Time: O(log n) – halves the range each iteration.

Space: O(1) – only a few variables.

#162 Find Peak Element

#875 Koko Eating Bananas