Guess Number Higher or Lower
Last Updated: March 29, 2026
Understanding the Problem
We need to find a secret number in the range [1, n] using only the guess API. Each call to guess(num) tells us one of three things: our guess is correct (returns 0), too high (returns -1), or too low (returns 1).
This is essentially a search problem. We're looking for a specific value in a sorted range, and we have a comparison oracle that tells us which direction to go. The range [1, n] is inherently sorted, which is a strong hint about the right technique.
The critical observation is that n can be as large as 2^31 - 1 (about 2.1 billion). Checking every number one by one would be painfully slow. But the sorted nature of the search space means we can eliminate half the candidates with each guess, and that's exactly what binary search does.
Key Constraints:
1 <= n <= 2^31 - 1→ n can be up to about 2.1 billion. A linear scan would require up to 2.1 billion API calls, which is far too slow. We need O(log n), and log2(2^31) = 31, so binary search would need at most 31 guesses.1 <= pick <= n→ The answer always exists within the range, so we're guaranteed to find it. No need to handle "not found" cases.
Approach 1: Linear Scan
Intuition
The simplest possible approach: just try every number from 1 to n until the API tells us we got it right. It's brute force, but it's guaranteed to find the answer since pick is somewhere in [1, n].
This is how you'd solve the problem if you had no cleverness at all. Start at 1, ask "is it 1?", then "is it 2?", and so on. Eventually you'll hit the right number.
Algorithm
- Start from number 1.
- Call
guess(i)for each numberifrom 1 to n. - If
guess(i)returns 0, returnias the answer.
Example Walkthrough
Input: n = 10, pick = 6
We call guess(1), guess(2), ..., guess(6). On the sixth call, guess(6) returns 0 and we return 6. We made 6 API calls to find the answer.
Code
- Time Complexity: O(n). In the worst case, the picked number is n, and we try every number from 1 to n before finding it. Each guess is O(1), so the total is O(n).
- Space Complexity: O(1). We only use a single loop variable. No extra data structures needed.
The linear scan ignores the "higher or lower" feedback entirely. What if we used that information to eliminate half the candidates with each guess?
Approach 2: Binary Search
Intuition
This problem is tailor-made for binary search. We have a sorted range [1, n], and the guess API acts as a comparator that tells us whether to go left or right. Instead of checking numbers one by one, we can guess the middle of our current range and instantly eliminate half the candidates.
Think about how you'd actually play this game with a friend. If the range is 1 to 100 and you guess 50, and they say "higher," you wouldn't start checking 51, 52, 53... You'd jump straight to 75, the midpoint of [51, 100]. Each guess cuts the problem in half.
With n up to 2^31 - 1, binary search needs at most 31 guesses. Compare that to 2 billion for the linear approach. That's the power of logarithmic search.
Binary search works because the search space [1, n] is ordered, and the guess API acts as a comparator. Each call to guess(mid) tells us which half of the current range contains the answer. By discarding the wrong half every iteration, we cut the search space in half each time.
After k guesses, the remaining search space has at most n / 2^k elements. When this drops to 1, we've found the answer. Solving n / 2^k = 1 gives k = log2(n), which is why binary search runs in O(log n) time. For n = 2^31, that's at most 31 iterations.
Algorithm
- Set
low = 1andhigh = n. - While
lowis less than or equal tohigh: - Compute the midpoint:
mid = low + (high - low) / 2. - Call
guess(mid). - If the result is 0, return
mid(we found the number). - If the result is -1, the pick is lower, so set
high = mid - 1. - If the result is 1, the pick is higher, so set
low = mid + 1. - Return -1 (should never reach here since the pick is guaranteed to exist).
Example Walkthrough
Code
- Time Complexity: O(log n). Each iteration halves the search space. Starting from n elements, we reach 1 element after at most log2(n) iterations. For n = 2^31 - 1, that's at most 31 iterations.
- Space Complexity: O(1). We only use three integer variables:
low,high, andmid. No recursion, no extra data structures.