Guess Number Higher or Lower

Guess Number Higher or Lower

What is this problem about?

The Guess Number Higher or Lower interview question is a classic game simulation. The system picks a secret number between 1 and n. You need to guess the number. If you guess wrong, an API guess(num) tells you whether your guess was too high (returns -1), too low (returns 1), or correct (returns 0). Your task is to find the secret number using the minimum number of guesses.

Why is this asked in interviews?

Companies like Google, Amazon, and Microsoft ask this coding problem as the foundational test of the Binary Search interview pattern. It evaluates whether a candidate understands the $O(\log n)$ search space reduction technique. It’s an "Easy" difficulty question that focuses on basic control flow, variable updating, and avoiding integer overflow during midpoint calculation.

Algorithmic pattern used

This problem is the textbook definition of Binary Search.

1. Initialize a search space with left = 1 and right = n.
2. Find the middle element mid = left + (right - left) / 2.
3. Call guess(mid).
4. If it returns 0, you found the number.
5. If it returns -1 (guess is too high), the secret number must be in the left half. Update right = mid - 1.
6. If it returns 1 (guess is too low), the secret number must be in the right half. Update left = mid + 1.

Example explanation

Suppose n = 10 and the secret number is 6.

1. left = 1, right = 10. mid = 5.
2. guess(5) returns 1 (too low). Update left = 6.
3. left = 6, right = 10. mid = 8.
4. guess(8) returns -1 (too high). Update right = 7.
5. left = 6, right = 7. mid = 6.
6. guess(6) returns 0. Found! Result: 6.

Common mistakes candidates make

• Integer Overflow: Calculating the midpoint as (left + right) / 2. If left and right are near the maximum 32-bit integer limit, their sum will overflow, causing a crash. Always use left + (right - left) / 2.
• Infinite Loops: Not updating left or right past mid (e.g., using left = mid). This causes the search space to get stuck on a single element.
• Misinterpreting API: Reversing the logic for 1 and -1 returned by the guess API.

Interview preparation tip

Whenever you have a sorted or monotonic search space (numbers 1 to N are inherently sorted), Binary Search is the answer. Memorize the left + (right - left) / 2 overflow protection trick, as it's a common "gotcha" in interviews.