DSA SheetEasy
EditorialPractice

BINARY SEARCH › INTRODUCTORY PROBLEMS

Guess Number Higher or Lower

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitioneach response eliminates half the possible picks

The picked number is hidden somewhere in the inclusive interval from 1 to n. A guess splits that interval at mid. If the API says the pick is higher, every number at or below mid is impossible; if it says the pick is lower, every number at or above mid is impossible. The response therefore tells you exactly which half to discard.

Keep the invariant that the picked number is always inside [left, right]. Start with the whole range, guess its middle, and move only the boundary that lies on the impossible side. When the response is 0, mid is the answer. Because each non-answer removes roughly half the remaining candidates, you need logarithmically many guesses rather than checking every number.

An inclusive binary-search interval for a hidden picked numberThe picture shows a horizontal inclusive number interval with left at one end, right at the other, and mid between them. A hidden pick sits in the retained portion. One half is shaded and labelled impossible after the API response, while the boundary on that side moves past mid. The remaining interval still contains the pick, making it clear that every answer discards half the candidates without discarding the solution.left = 1mid guess 8 → APIright = 15123456789101112131415TOO LOW → discard 1…8TOO HIGH → discard 8…1512345678910111213★1415891011121314151234★567inclusive interval [1…15]discarded half: impossibleretained intervalnew left = 9 right = 15★ hidden pick = 13discarded half: impossibleretained intervalnew left = 1 right = 7★ hidden pick = 4Every response removes a half; the hidden pick stays in the retained interval.

Approach

  1. Set left to 1 and right to n, because every allowed pick is initially a candidate and excluding either endpoint could lose the answer.
  2. While left <= right, compute mid as left + (right - left) / 2, because the direct sum left + right can overflow a 32-bit integer even though the final midpoint is valid.
  3. Call the guess API with mid, because its return value identifies whether mid is the answer or which side of the interval remains possible.
  4. If the response is 0, return mid immediately, because the API has confirmed the hidden number exactly.
  5. If the response is -1, set right to mid - 1, because mid and every larger number are too high and must not remain candidates.
  6. If the response is 1, set left to mid + 1, because mid and every smaller number are too low and must not remain candidates.
  7. Return -1 only after the loop as a defensive fallback, because a valid pick must be found while the invariant interval is nonempty.

Complexitythe interval shrinks geometrically

MEASUREBOUNDWHY
TimeO(log n)After each non-answer, the number of possible values is reduced to at most about half, and each iteration performs one constant-time API call and boundary update. The loop therefore cannot run more than logarithmically many times in n.
SpaceO(1)Only left, right, mid, the API result, and a constant amount of temporary state are stored. This bound does not degrade for any position of the picked number, and the returned integer is output rather than working memory.
n is the upper endpoint of the initial range; the returned integer is required output and is excluded from extra space.

Annotated solutionC++ · iterative binary search · overflow-safe boundaries

CPPMaintain an inclusive interval and discard the impossible half after each API response.
#include <vector>
using namespace std;

class Solution {
public:
    int guessNumber(int n, int pick) {
        auto guess = [&](int num) {
            if (num == pick) return 0;
            return num > pick ? -1 : 1;
        };

        long left = 1;
        long right = n;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            int result = guess((int) mid);

            if (result == 0) {
                return (int) mid;
            } else if (result == -1) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
};

The two boundary updates are the heart of the solution. Once mid is known to be too high or too low, it cannot be the answer, so the new interval starts at mid + 1 or ends at mid - 1. Using those strict updates guarantees that the interval shrinks; the long variables also make the midpoint arithmetic safe at the largest allowed n.

Common mistakesthree lines that quietly break the search

Previous · Binary Search