374. Guess Number Higher or Lower - Detailed Explanation

A number between 1 and n has been picked. You may call a provided function guess(num), which returns -1 if your guess is too high, 1 if it is too low, and 0 if it is correct. Find the number in as few calls as possible. This is binary search stripped of everything else, which makes it a common phone screen opener.

It appears in the binary search section of LeetCode 75.

Examples

Constraints

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

That upper bound is the entire reason this question is not trivial, and it is covered below.

Which pattern this problem belongs to

This is the modified binary search pattern. Ordinary binary search looks for a value in a sorted array by comparing against the midpoint. Here there is no array at all. The search space is the range of candidate answers from 1 to n, and the comparison comes from the guess function rather than from memory.

That shift matters well beyond this question. Once you can binary search a range of answers rather than a container, questions like Koko Eating Bananas become approachable, because they search a range of speeds using a feasibility test in place of a comparison.

Approach

Keep a low and a high bound, starting at 1 and n. Guess the midpoint. If the answer says too high, the pick is below the midpoint, so move high down. If it says too low, move low up. If it says zero, you are done. Each call halves the remaining range, so the number of calls is O(log n).

Two details decide whether the implementation is correct.

The midpoint must not overflow. With n up to 2^31 - 1, computing (low + high) / 2 in a language with 32-bit integers overflows and produces a negative midpoint. Write low + (high - low) / 2 instead, which never exceeds high. Python integers are arbitrary precision so the naive form works there, but the Java version must use the safe form and interviewers watch for it.

The sign convention is backwards from intuition. The API returns -1 when your guess is too high, not when it is too low. Reading it the other way inverts the search and loops forever. Say the convention out loud before writing the branch.

Python code

def guessNumber(n):
    """Binary search over the answer range. O(log n) calls, O(1) space."""
    low, high = 1, n
    while low <= high:
        mid = low + (high - low) // 2
        result = guess(mid)
        if result == 0:
            return mid
        if result < 0:        # mid is too high, search lower
            high = mid - 1
        else:                 # mid is too low, search higher
            low = mid + 1
    return -1                 # unreachable given the constraints

Java code

public int guessNumber(int n) {
    int low = 1, high = n;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // overflow safe
        int result = guess(mid);
        if (result == 0) return mid;
        if (result < 0) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

Complexity

At the maximum n, that is about 31 calls, which is a good concrete number to quote.

Common mistakes

• Writing (low + high) / 2 in Java. It overflows at large n and produces a negative midpoint. The failing case is exactly the maximum allowed input, so it passes small tests and fails the real ones.
• Inverting the sign. A return of -1 means your guess was too high. Getting this backwards gives an infinite loop rather than a wrong answer, which is harder to debug under time pressure.
• Using low < high with the wrong update. Mixing a strict loop condition with high = mid - 1 can skip the answer. Pair low <= high with mid - 1 and mid + 1, which is the convention that is hardest to get wrong.
• Calling guess more than once per iteration. Each call counts, so store the result in a variable and branch on it.

Related problems

• Find Peak Element, which binary searches without a sorted array by comparing neighbors.
• Koko Eating Bananas, which binary searches a range of answers with a feasibility test.
• First Bad Version, which is nearly the same question with a different API.

How to Prepare

• Memorize the overflow-safe midpoint. Write low + (high - low) / 2 every time, in every language, so it is automatic.
• Read the API contract aloud before coding. Most failures on this question are a misread sign, not a flawed algorithm.
• Learn the answer-space variant. Binary searching a range rather than an array is the version that shows up in harder questions, and Grokking the Coding Interview teaches it as its own pattern. The short version is in the most common LeetCode patterns.