Guess Number Higher or Lower
Find a hidden number in [1, n] with binary search, guessing the middle of the remaining range and using the guess() answer to discard half of it.
Problem Understanding
Guess Number Higher or Lower (LeetCode 374): a number between 1 and n has been picked. Each time you guess, a predefined guess(num) API tells you -1 if the pick is lower than num, 1 if it is higher, or 0 if you are right. Return the picked number.
Examples: n = 10, pick = 6 → 6; n = 1, pick = 1 → 1; n = 2, pick = 1 → 1.
The Intuition: The Children's Game, Played Optimally
In "I'm thinking of a number", the best guess is always the middle of what is still possible: whatever the answer, half the candidates are gone.
- Keep a range [lo, hi] where the pick must be.
- Guess its middle.
- Keep the half guess() points to, dropping mid as well.
It is Introduction to Binary Search with the comparison hidden behind an API, like First Bad Version, except that here a single guess can be exactly right.
Interactive Walkthrough
n = 10 · AT MOST 4 GUESSES
WHOLE RANGE
1 … n (the outlined run is [lo, hi])
lo
hi
guess(mid)
:
Guesses
0
Answer
:
The pick is somewhere in [1, 10]: lo = 1, hi = 10
Next
Guess the middle of [1, 10]: mid = 5. guess(5) returns 1
n
pick
The outlined run is the range still possible; ruled-out numbers are greyed and the current guess is filled. Set n and pick, or try n = 31 to watch five guesses halve 31 numbers down to one.
Dry Run Table
Input: n = 10, pick = 6.
| lo | hi | mid | guess(mid) | Next |
|---|---|---|---|---|
| 1 | 10 | 5 | 1 | lo = 6 |
| 6 | 10 | 8 | -1 | hi = 7 |
| 6 | 7 | 6 | 0 | return 6 |
Answer: 6, in 3 guesses.
The Solution Template
Standard binary search on [1, n], with guess() as the comparison. The final return is never reached for valid input.
Guess Number Higher or Lower Code
1var guessNumber = function(n) {2 let lo = 1, hi = n;3 while (lo <= hi) {4 const mid = Math.floor((lo + hi) / 2);5 const res = guess(mid);6 if (res === 0) {7 return mid;8 }9 if (res < 0) {10 hi = mid - 1;11 } else {12 lo = mid + 1;13 }14 }15 return -1;16};
Edge Cases & Common Mistakes
- Reading -1 backwards: -1 means the pick is lower, so move hi down.
- Overflow: with n near 2^31 - 1, (lo + hi) / 2 overflows in Java, C++ and C; use lo + (hi - lo) / 2.
- Keeping mid in the range: after a non-zero answer mid is ruled out; use mid - 1 or mid + 1, or the loop can stall.
- n = 1: the first guess is right.
Summary
Binary search [1, n]: guess the middle, return it on 0, otherwise keep the half guess() points to. O(log n) guesses, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet