Guess Number Higher or Lower — Binary Search with API [LC 374]

Problem Statement#

We are playing a guessing game. I pick a number between 1 and n. You call guess(num), which returns:

• -1 if num is higher than the picked number
• 1 if num is lower than the picked number
• 0 if num equals the picked number

Return the number that was picked.

Constraints:

• 1 <= n <= 2^31 - 1
• 1 <= pick <= n

Example 1:

Input:  n = 10, pick = 6
Output: 6
Explanation: guess(6) returns 0 → return 6.

Example 2:

Input:  n = 1, pick = 1
Output: 1
Explanation: Only one number, guess(1) = 0 directly.

Example 3:

Input:  n = 2, pick = 1
Output: 1
Explanation: guess(2) = -1 (too high), so lo=1, hi=1, mid=1, guess(1)=0.

Why This Problem Matters#

LC 374 is the purest possible instantiation of binary search: an ordered search space [1..n], three outcomes at each step, and a black-box oracle (guess()) that tells you which direction to go. The problem has zero algorithmic complexity — you just implement the binary search template correctly.

That is precisely why it matters in interviews. It is a diagnostic question. The interviewer is not testing creativity; they are verifying that you have the binary search template memorised cold — correct midpoint calculation, correct lo/hi update rules for each return value, and correct loop termination. If you get any detail wrong here, it raises questions about your reliability on harder binary search problems.

The problem also models a broad class of interactive problems where you make guesses and receive structured feedback. The same template applies to guessing games in system design (exponential back-off finding a safe rate limit), black-box binary search in competitive programming, and the classic "find a number in a black-box sorted function" category.

The Core Insight#

The search space [1..n] is implicitly sorted. Every call to guess(mid) tells you:

• 0 — you are exactly at the answer. Return immediately.
• -1 — your guess is too high. The answer is in [lo, mid-1]. Set hi = mid - 1.
• 1 — your guess is too low. The answer is in [mid+1, hi]. Set lo = mid + 1.

This is the standard inclusive binary search template (lo <= hi) with three-way branching. The only difference from LC 704 is that the comparison is replaced by a call to guess().

Critical midpoint formula: mid = lo + (hi - lo) // 2.

With n up to 2^31 - 1, if you compute (lo + hi) // 2, the sum can overflow a 32-bit integer in languages like Java or C. The subtraction form lo + (hi - lo) // 2 is always safe.

Return value semantics (common confusion):

• guess(mid) == -1 means mid > pick, so narrow to the left.
• guess(mid) == 1 means mid < pick, so narrow to the right.

The sign feels backwards to many people. Remember it as: the API is telling you whether your guess needs to go lower (-1 = you guessed too high) or higher (1 = you guessed too low).

Visual Dry Run#

n = 10, pick = 6

n = 10, pick = 10

Common Mistakes#

1. Swapping the return-value conditions. Writing if guess(mid) == 1: hi = mid - 1 instead of lo = mid + 1 is the most common error. The 1 from guess() means your guess is too low — you must move right, not left.

2. Using (lo + hi) // 2 when n can be near 2^31 - 1. In Python this is fine (arbitrary-precision integers), but in Java, C, and JavaScript, lo + hi can overflow. Always use lo + (hi - lo) // 2.

3. Using lo < hi instead of lo <= hi. With <, the loop exits before checking the last remaining element, causing a miss when the answer is the final candidate.

4. Not returning inside the guess(mid) == 0 branch. Some implementations forget return mid and fall through to the loop update, corrupting lo or hi.

5. Using hi = n + 1 (exclusive right boundary). This works but requires a different template (lo < hi with hi = mid). Mixing exclusive-right with the inclusive template breaks correctness.

Solutions#

Python#

# The guess() API is pre-defined for you in the LeetCode environment.
# def guess(num: int) -> int:
#   -1 if num > pick
#    1 if num < pick
#    0 if num == pick
 
def guessNumber(n: int) -> int:
    lo, hi = 1, n                              # inclusive search range [1, n]
 
    while lo <= hi:                            # continue while range is non-empty
        mid = lo + (hi - lo) // 2             # safe midpoint — no overflow
 
        result = guess(mid)                    # call the oracle API
 
        if result == 0:                        # exact match
            return mid
        elif result == -1:                     # our guess is too high — search left half
            hi = mid - 1
        else:                                  # result == 1 — our guess is too low — search right half
            lo = mid + 1
 
    return -1                                  # unreachable if pick is always in [1, n]

JavaScript#

/**
 * @param {function} guess
 * @return {function}
 */
var solution = function(guess) {
    return function(n) {
        let lo = 1;                            // inclusive lower bound
        let hi = n;                            // inclusive upper bound
 
        while (lo <= hi) {                     // loop while range is non-empty
            const mid = lo + Math.floor((hi - lo) / 2); // safe midpoint
 
            const result = guess(mid);         // call the oracle API
 
            if (result === 0) {                // exact match — done
                return mid;
            } else if (result === -1) {        // guess too high — narrow left
                hi = mid - 1;
            } else {                           // result === 1 — guess too low — narrow right
                lo = mid + 1;
            }
        }
 
        return -1;                             // unreachable under valid constraints
    };
};

Complexity Analysis#

Follow-up Questions#

1. LC 375 — Guess Number Higher or Lower II. The variant where each wrong guess costs you the guessed number, and you must minimise the worst-case cost. This requires dynamic programming, not binary search.
2. What is the minimum number of guesses needed for n = 2^31 - 1? At most 31 guesses, since log2(2^31) = 31.
3. Generalise: binary search on a black-box monotone function. If you have a function f(x) that is monotone and you can evaluate it, you can binary search for the transition point — the exact same template.
4. Interactive problems on Codeforces / competitive programming. The same loop applies. The only difference is that the oracle is a judge that reads your output and replies.

This Pattern Solves#

• LC 374 — Guess Number Higher or Lower (this problem)
• LC 278 — First Bad Version (same template, different oracle)
• LC 704 — Binary Search (oracle is array lookup)
• Any interactive / black-box monotone search problem

Key Takeaway#

LC 374 is the purest binary search: three-way oracle, inclusive range, and nothing else. The two things you must get perfectly right are (1) the safe midpoint formula lo + (hi - lo) // 2 and (2) the API return-value semantics: -1 means your guess is too high (move left), 1 means too low (move right). Get these two right and every interactive binary search problem becomes mechanical.

Key Takeaways#

• LC 374 is the diagnostic binary search problem — interviewers use it to verify the template is memorised cold, not to test creativity.
• The safe midpoint lo + (hi - lo) // 2 is mandatory: with n up to 2^31 - 1, the naive (lo + hi) // 2 overflows in Java, C++, and JavaScript.
• API return-value semantics: -1 means your guess is too HIGH (move left, hi = mid - 1); 1 means too LOW (move right, lo = mid + 1).
• Use while lo <= hi (inclusive) — switching to lo < hi causes the last candidate to be skipped when the loop condition fails.
• Return immediately when guess(mid) == 0 — do not fall through to the pointer-update logic or you will corrupt the range.
• This same template applies to LC 278 (First Bad Version), LC 704 (Binary Search), and any black-box monotone search problem.
• Worst-case calls: floor(log2(n)) + 1 — for n = 2^31 - 1, that is at most 31 API calls.