Guess Number Higher or Lower: Binary Search Without an Array
Solve Guess Number Higher or Lower with binary search — treat the guess API as a comparison oracle, halve the range each call, and find the pick in O(log n).
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You already know this algorithm. Every kid who has played "I'm thinking of a number between 1 and 100" figures out that guessing 50 first beats guessing 1, 2, 3, ... — because "too high" or "too low" kills half the possibilities in one shot.
Guess Number Higher or Lower (LeetCode 374) is that game, formalized. It teaches the single most liberating fact about binary search: you don't need an array. You need a range and an oracle — any function that tells you "go lower" or "go higher". Once that clicks, a whole family of problems (bad versions, square roots, capacity planning) stops looking like array problems and starts looking like guessing games.
The problem
You are guessing a hidden number pick between 1 and n. You can't see it, but a predefined API guess(num) compares your guess to it:
- returns
-1— your guess is higher than the pick (aim lower) - returns
1— your guess is lower than the pick (aim higher) - returns
0— your guess is the pick
Return the hidden number.
Input: n = 10, pick = 6
Output: 6
guess(5) → 1 (pick is higher)
guess(8) → -1 (pick is lower)
guess(6) → 0 (found it)Two things in the setup matter more than they look:
ncan be as large as2³¹ − 1— over two billion candidates. Anything linear is dead on arrival.- The API is the only way to learn anything about the pick. Your entire algorithm is a strategy for spending API calls wisely.
The brute force baseline
Ask about every number in order until the API says yes:
var guessNumber = function (n) {
for (let i = 1; i <= n; i++) {
if (guess(i) === 0) return i;
}
};This works and is O(n) — but O(n) here means up to 2.1 billion API calls when the pick sits at the top of the range. Worse, it throws away information: when guess(1) returns 1, you've learned the pick is above 1, yet the scan dutifully asks about 2 next. Every answer is a comparison, and a comparison can eliminate far more than one candidate at a time.
The key insight: the API is your comparison oracle
Look at the classic binary search loop. Its engine is one line:
if (nums[mid] < target) → search right half
else → search left halfBinary search never needed the array itself — it needed that comparison. Any function that consistently answers "is the answer left or right of here?" can drive the same halving loop. That's the binary search with oracle pattern: guess(mid) is a drop-in replacement for comparing nums[mid] against target.
So reframe the problem. Your search space is the integer range [1, n], not an array. Each answer discards half of whatever range remains:
guess(mid) === 1→ pick is abovemid→ everything up to and includingmidis eliminated.guess(mid) === -1→ pick is belowmid→ everything frommidup is eliminated.guess(mid) === 0→ done.
Halving a two-billion-wide range takes at most 31 steps. Thirty-one API calls instead of two billion — same answer, ~70 million times fewer questions.
The optimal solution
var guessNumber = function (n) {
let left = 1, right = n;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const result = guess(mid);
if (result === 0) return mid;
if (result === 1) left = mid + 1;
else right = mid - 1;
}
};This is the textbook inclusive-bounds template, with three details worth internalizing:
- Call the API once per iteration and store the result.
guess(mid)is a function call, not an array read. Calling it in a chain ofifs triples your cost — and in real systems the oracle is often a network request or an expensive check. result === 1means go up. The return value describes the pick relative to your guess:1= pick is higher. Misread it as a verdict on your guess and both branches flip — the search walks away from the answer.midis fully excluded after each test. You asked the oracle aboutmiddirectly, so both shrinks skip it (mid + 1/mid − 1). The range strictly shrinks every iteration — no infinite loop possible — and since the pick is guaranteed to exist, the loop always returns.
In JavaScript, Math.floor((left + right) / 2) is safe even at n = 2³¹ − 1, because JS numbers represent integers exactly up to 2⁵³. Porting to Java or C++? left + right overflows a 32-bit int — write left + (right - left) / 2 there instead.
Prefer watching to reading? Step through it interactively and watch the range collapse guess by guess.
Walkthrough: n = 10, pick = 6
| Step | left | right | mid | guess(mid) | Meaning | Action |
|---|---|---|---|---|---|---|
| 1 | 1 | 10 | 5 | 1 | pick is higher | left = 6 |
| 2 | 6 | 10 | 8 | -1 | pick is lower | right = 7 |
| 3 | 6 | 7 | 6 | 0 | found it | return 6 |
Three API calls to pin one number out of ten. Each answer slices the range: [1, 10] → [6, 10] → [6, 7] → done. Step 3 is the floor-division moment — mid = ⌊(6 + 7) / 2⌋ = 6 rounds down, which is exactly why the left = mid + 1 shrink is required to make progress when the range is two wide.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Linear scan | O(n) | O(1) | one API call per candidate; up to 2³¹ − 1 calls |
| Binary search | O(log n) | O(1) | each call halves the range; ≤ 31 calls for any valid n |
Both use constant space — the win is purely in API calls, the honest cost model for oracle problems. When the expensive operation is the question, log n questions versus n questions is the entire ballgame.
Common mistakes
- Flipping the sign convention.
guess(mid) === 1means the pick is higher than your guess, soleftmoves up. Reading1as "your guess is high" inverts both branches and the search diverges. Sign conventions genuinely differ across platforms — re-read the API contract before writing the branches. - Computing mid as
(left + right) / 2in fixed-int languages. Withnnear 2³¹ − 1, the sum overflows in Java/C++/C#. Useleft + (right - left) / 2. - Calling
guess(mid)more than once per iteration.if (guess(mid) === 0) ... else if (guess(mid) === 1) ...triples your API calls for zero information gain. Store the result once. - Starting at
left = 0. The range is[1, n]. Starting at 0 happens to work here, but in stricter oracle problems, querying outside the valid range is an error. - Using
while (left < right)withmid ± 1shrinks. That loop condition pairs withright = mid(keep-the-candidate style, as in First Bad Version). Heremidis definitively ruled out each turn, soleft <= rightwith both-sides-exclusive shrinks is the right pairing. Mixing templates is the number-one source of binary search off-by-ones.
Where this pattern shows up next
Guess Number is the cleanest possible statement of "binary search = range + oracle." The rest of the family swaps in different oracles:
- Binary Search — the array version, where the oracle is a plain
nums[mid]comparison. The template is identical. - First Bad Version — another API oracle, but you're finding a boundary, not an exact match, so the loop shape changes to
left < right. - Sqrt(x) — the oracle becomes a computation you write yourself (
mid * mid <= x), searching a numeric range for the last value that passes. - Search in Rotated Sorted Array — back to arrays, but the comparison needs an extra deduction step to decide which half is trustworthy.
FAQ
What does the guess API return in Guess Number Higher or Lower?
guess(num) returns one of three values: -1 if your guess is higher than the pick, 1 if your guess is lower than the pick, and 0 if your guess equals the pick. A return of 1 means "go higher", so you move left to mid + 1.
Why does binary search work here without a sorted array?
Because binary search never actually required an array — it requires an ordered search space and a comparison that tells you which side of the current probe the answer lies on. The range [1, n] is ordered, and guess(mid) answers "lower or higher?" consistently. That pair — ordered range plus a reliable oracle — is the real precondition, and it's why the same loop solves problems like computing square roots or finding the first failing version.
What is the time complexity of Guess Number Higher or Lower?
O(log n) time and O(1) space. Every call to guess(mid) eliminates half of the remaining range, so a range of size 2³¹ − 1 (the maximum n) is resolved in at most 31 API calls. The linear alternative — guessing 1, 2, 3, ... — is O(n), which can mean over two billion calls.
Why do some solutions write mid as left + (right - left) / 2?
To avoid integer overflow. In languages with fixed 32-bit integers (Java, C++, C#), left + right can exceed the int maximum when n is near 2³¹ − 1, producing a negative number and a broken search. left + (right - left) / 2 computes the same midpoint without ever forming the oversized sum. In JavaScript, Math.floor((left + right) / 2) is safe because numbers are 64-bit floats that represent integers exactly up to 2⁵³.
How is this different from First Bad Version?
Both replace the array with an API oracle, but they search for different things. Guess Number looks for an exact match — the oracle can say "found it" — so the loop runs while (left <= right) and excludes mid on both shrinks. First Bad Version looks for a boundary (the first failing version); its oracle only answers yes/no, so mid must stay in range when it answers "bad" (right = mid), and the loop runs while (left < right). Choosing the right template for match-vs-boundary is most of the difficulty in binary search problems.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.