Guess Number Higher or Lower (LeetCode 374): Binary Search on a Hidden Target

Guess Number Higher or Lower is LeetCode 374. It takes the binary search template you already know from searching a sorted array and replaces the array lookup with an API call. The mechanics are identical; only the comparison step changes.

If you have solved LeetCode 704 Binary Search, this problem should feel like putting on a familiar pair of shoes. If you have not, it is worth reading that post first.

The problem

You are playing a guessing game. The system picks a number between 1 and n. You call guess(num) to check your guess:

• Returns 0 if num is the correct answer.
• Returns -1 if num is too high (the target is lower).
• Returns 1 if num is too low (the target is higher).

Write a function guessNumber(n) that returns the target number.

The constraint is that you should minimize the number of calls to guess. A linear scan from 1 to n works but can take up to n calls. Binary search takes at most log2(n) calls.

How the range narrows

The number line below shows n=16 with the target hidden at 11. Watch how each guess cuts the remaining range in half.

Three guesses reduce the range from 16 numbers down to 3. One more guess finds the target. That is the power of halving: every step eliminates half the remaining possibilities, regardless of where the target actually sits.

The approach

Binary search works because the guess API gives you directional information. When guess(mid) returns 1, you know the target is somewhere above mid, so everything at or below mid can be discarded. When it returns -1, everything at or above mid can be discarded. When it returns 0, you have your answer.

This is exactly what you do when searching a sorted array, except there you compare arr[mid] against a known target. Here the comparison is hidden inside guess. The loop structure and the boundary updates are unchanged.

Keep lo and hi as inclusive bounds. Compute mid = lo + (hi - lo) // 2 to avoid overflow. Update lo = mid + 1 when the guess is too low, and hi = mid - 1 when the guess is too high. The loop condition is lo <= hi because the range is inclusive on both ends.

The solution

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

A few things worth noting:

• lo, hi = 1, n initializes the range to the full problem space. The target could be any number from 1 to n.
• mid = lo + (hi - lo) // 2 is the overflow-safe midpoint. In Python it does not matter, but it is the right habit.
• result == -1 means the target is lower than mid, so you set hi = mid - 1 to exclude mid and everything above it.
• result == 1 means the target is higher than mid, so you set lo = mid + 1 to exclude mid and everything below it.
• The loop exits when lo > hi, but in this problem the target is always present, so you will always return inside the loop.

Step-by-step walkthrough

Here is the full search for n=16, target=11. Use the buttons to step through each guess.

Four guesses to find a number in a range of 16. For n=1,000,000, you would need at most 20 guesses. The logarithm grows so slowly that even massive ranges take only a handful of calls.

Complexity analysis

Each iteration of the loop cuts the search range in half. Starting with n candidates, after k iterations you have at most n / 2^k remaining. The loop ends when this hits 1 or the target is found, so the number of iterations is at most log2(n).

Space is O(1). You use three variables (lo, hi, mid) and the comparison result, all constant regardless of n.

Building blocks

This problem uses one building block: the binary search template with inclusive bounds.

The template appears in every problem where you need to find a specific value or boundary in a space you can query. What changes between problems is only the query:

• In Binary Search (704), the query is arr[mid] == target.
• In Guess Number Higher or Lower (374), the query is guess(mid) == 0.
• In First Bad Version (278), the query is isBadVersion(mid).
• In Koko Eating Bananas (875), the query checks whether a speed can finish all bananas in h hours.

The loop, the midpoint calculation, and the boundary updates are the same in all of them. Recognizing this means you only need to understand one template, then plug in the right comparison for each problem.

Edge cases

n = 1. The only possible answer is 1. lo = hi = 1, mid = 1, and guess(1) returns 0 immediately. The loop runs once and returns.

Target is at n. lo and hi converge upward until both equal n. guess(n) returns 0 and you return n. No special handling needed.

Target is at 1. lo and hi converge downward until both equal 1. Same outcome.

Even vs odd n. The midpoint formula handles both. lo + (hi - lo) // 2 always rounds down, so if lo = 9 and hi = 11, mid = 10. No off-by-one risk.

From understanding to recall

Reading a solution and understanding it is the easy part. The hard part is reproducing it under pressure three weeks from now when the details have faded.

The specific things you need to retain here are small: lo = 1, not lo = 0; check result == -1 for "too high"; check result == 1 for "too low". These are easy to mix up when you are nervous in an interview and second-guessing yourself.

Spaced repetition handles this. You type the solution from memory today, then again tomorrow, then in three days, then a week. Each session is short, but the repetition burns the details in. After a few rounds you write the loop condition and the API result checks without hesitation, and you can spend your focus on harder parts of whatever problem you are actually solving.

Related posts

• Binary Search (LeetCode 704): The Foundation - The core template with sorted arrays, off-by-one analysis, and when to use <= vs <
• First Bad Version (LeetCode 278) - Binary search on a boolean predicate to find a hidden boundary
• Koko Eating Bananas (LeetCode 875) - Binary search on the answer space, a more advanced application of the same template