Guess Number Higher or Lower

Problem in plain words

A number has been chosen secretly from 1 to n. You can call a provided function guess(num), which returns -1 if your number is too high (the secret is smaller), 1 if it is too low (the secret is larger), and 0 if you got it. Return the secret number.

Example: n = 20 and the secret is 13. Guessing 10 returns 1 (go higher), guessing 15 returns -1 (go lower), and so on until a guess returns 0.

Intuition

Every answer from guess cuts the range of possible values roughly in half — the textbook setup for binary search. Keep a window [lo, hi] that always contains the secret, probe the middle, and shrink toward the side the feedback points to.

Approach

1. Set lo = 1 and hi = n.
2. While lo <= hi, compute mid = lo + (hi - lo) / 2.
3. If guess(mid) == 0, return mid.
4. If it returns -1, the secret is smaller: set hi = mid - 1. If it returns 1, set lo = mid + 1.

Dry run

n = 20, secret 13.

Java solution

/**
 * Forward declaration of guess API.
 * int guess(int num) returns -1 if num is higher than the pick,
 * 1 if num is lower than the pick, otherwise 0.
 */
public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int lo = 1;
        int hi = n;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int result = guess(mid);
            if (result == 0) {
                return mid;
            } else if (result < 0) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return -1; // unreachable when the pick is in [1, n]
    }
}

Python solution

# The guess API is already defined for you.
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        lo, hi = 1, n
        while lo <= hi:
            mid = (lo + hi) // 2
            result = guess(mid)
            if result == 0:
                return mid
            if result < 0:
                hi = mid - 1
            else:
                lo = mid + 1
        return -1

Complexity

Edge cases and common mistakes

• Overflow in Java — n can be 2^31 - 1, so (lo + hi) / 2 overflows. Use lo + (hi - lo) / 2. Python integers do not overflow.
• Reading the feedback backwards — -1 means your guess is too high, so move hi down, not lo up.
• `n = 1` — the first guess is 1 and returns 0.
• Infinite loops — always move past mid (mid - 1 or mid + 1) so the window shrinks every step.