Guess Number Higher or Lower

Problem Statement

You pick numbers from 1..n. An API guess(num) returns -1 (your guess is too high), 1 (too low), or 0 (correct). Find the picked number using as few guesses as possible.

Example

Input:  n = 10, pick = 6
Output: 6

Approach

This is textbook binary search over the range [1, n], driven by the API instead of array comparisons. Guess the midpoint; on -1 search the lower half, on 1 the upper half, on 0 return it.

Complexity

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

Solution Code

Python

def guessNumber(n):
    lo, hi = 1, n
    while lo <= hi:
        mid = (lo + hi) // 2
        r = guess(mid)        # -1 too high, 1 too low, 0 correct
        if r == 0:
            return mid
        elif r < 0:
            hi = mid - 1
        else:
            lo = mid + 1
    return -1

Java

int guessNumber(int n) {
    int lo = 1, hi = n;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int r = guess(mid);
        if (r == 0) return mid;
        else if (r < 0) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}

C++

int guessNumber(int n) {
    int lo = 1, hi = n;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int r = guess(mid);
        if (r == 0) return mid;
        else if (r < 0) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}

Key Takeaways

• The guess() API plays the role of an array comparison.
• Overflow-safe midpoint matters because n can be close to INT_MAX.
• Reference: LeetCode 374 (Guess Number Higher or Lower).