Interview Problem Explained: Guess Number Higher or Lower (LeetCode 374, Binary Search)

Guess Number Higher or Lower: Problem Statement

This problem is a simple number guessing game. The system secretly picks a number (pick) between 1 and n. You can call a predefined function guess(num) to find out if your guess (num) is higher, lower, or equal to pick. Your goal is to find pick using the minimum number of calls to guess.

The guess(num) function returns:

• 1: Your guess num is higher than pick.

• 1: Your guess num is lower than pick.

• 0: Your guess num is equal to pick.

Tip: This is LeetCode Problem 374. LeetCode’s problem statements are often concise and may confuse learners. Codetree provides additional explanations and examples for deeper understanding.

Step 1. Naive Approach

Idea

What’s the most straightforward solution? Simply try every number from 1 to n, calling guess() for each one. This is a linear search approach: "Is it 1? Is it 2? Is it 3? ..."—checking every possibility in order.

Logic Breakdown

1. Loop through every number k from 1 to n.

2. For each k, call guess(k).

3. If guess(k) returns 0, then k is the answer. Return k and stop searching.

Code Implementation

def guessNumber(self, n: int) -> int:
    # Check every number from 1 to n sequentially.
    for k in range(1, n + 1):
        # Call guess(k) to check if it's the answer.
        if guess(k) == 0:
            # If found, return k.
            return k

Time & Space Complexity Analysis

• Time Complexity: O(n) In the worst case (if the answer is n), you must call guess() n times. Since n can be as large as 2^31−1, this approach leads to excessive calls and will cause a time limit exceeded error.

• Space Complexity: O(1) Only the loop variable k is used; no extra memory is required.

Step 2. Binary Search Approach

Idea

The problem with Step 1 is that it makes too many unnecessary guesses.

The guess() function doesn’t just say "right or wrong"—it tells you if your guess is too high or too low. This directionality allows you to drastically reduce the search space. Since the numbers are sorted, you can apply binary search: always guess the middle value, and use the result to discard half the remaining possibilities each time.

The key idea: "From the current possible range, guess the middle number, and use the result to halve the search space."

Logic Breakdown

1. Set the search range from left = 1 to right = n.

2. While left is less than or equal to right (i.e., the search space is valid):

3. Compute the midpoint: mid = (left + right) // 2.

4. Call guess(mid) and store the result in res.

5. Adjust the search range based on res:

   • If res == 0 (correct): Return mid.

   • If res == 1 (guess is too high): Move the search range to the left (right = mid - 1).

   • If res == -1 (guess is too low): Move the search range to the right (left = mid + 1).

Code Implementation

def guessNumber(self, n: int) -> int:
    left, right = 1, n

    # Continue while the search range is valid
    while left <= right:
        # In Python, integer overflow isn't an issue, so this is safe
        mid = (left + right) // 2
        res = guess(mid)

        if res == 0:
            # Found the answer
            return mid
        elif res == 1:
            # Guess is too high; discard left half
            right = mid - 1
        else:  # res == -1
            # Guess is too low; discard right half
            left = mid + 1

Time & Space Complexity Analysis

• Time Complexity: O(log n) Each step halves the search range. The number of steps needed to reduce n to 1 is proportional to log n. Thus, the time complexity is O(log n), making it extremely fast even for large n.

• Space Complexity: O(1) Only a few variables (left, right, mid) are used.

To practice: Quickly Find Numbers

Frequently Asked Questions

Q: Why do we use while left <= right instead of while left < right?

A: When left == right, there’s only one value left to check — it could be the answer. Skipping it would cause errors.

Q: Why use while left <= right instead of while left < right?

A: When left equals right, there is only one number left to check, which could be the answer. We must check this final value.

Q: Can this be implemented recursively?

A: Yes, but an iterative solution is often preferred to avoid stack overflow on large inputs.

How to Prepare for Interviews with the Guess Number Higher or Lower Problem

This problem is commonly used in interviews to assess your basic algorithm knowledge and problem-solving skills.

1. Pattern Recognition: When you see "find a value in a sorted range," you should immediately think of binary search. Here, the range from 1 to n is implicitly sorted.

2. Clear Communication: Practice explaining: "Linear search is O(n) and inefficient. Since guess() provides direction, we can optimize to O(log n) using binary search."

3. Boundary Handling: Many mistakes in binary search come from incorrectly updating left, right, or the loop condition. Understand and be able to explain why you use left <= right and how you update the boundaries.

4. Extensions: Binary search can be adapted to find the first/last occurrence, search for a condition, or optimize thresholds. Master the core logic so you can adapt to these variants.

Similar Problems to Practice

• Search Insert Position

• First Bad Version

• First Occurrence of a Number

How to review after solving this problem:

1. Finding other problems that require searching for a value or condition in sorted data, and think about how to adapt the left, right, and mid logic.

2. Summarizing the solution in one sentence (e.g., "Optimized linear search from O(n) to O(log n) using binary search and directional feedback.").

3. Manually tracing how left, right, and mid change for small n (e.g., 10) to deepen your understanding of boundary handling.