Guess Number Higher or Lower — Editorial

Opening the reading…

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.

Approach

Set left to 1 and right to n, because every allowed pick is initially a candidate and excluding either endpoint could lose the answer.

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.

Call the guess API with mid, because its return value identifies whether mid is the answer or which side of the interval remains possible.

If the response is 0, return mid immediately, because the API has confirmed the hidden number exactly.

If the response is -1, set right to mid - 1, because mid and every larger number are too high and must not remain candidates.

If the response is 1, set left to mid + 1, because mid and every smaller number are too low and must not remain candidates.

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

MEASURE	BOUND	WHY
Time	O(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.
Space	O(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.