LeetCode 374: Guess Number Higher or Lower (Binary Search on Feedback API)

2026-03-26 · LeetCode · Binary Search / Interactive API

Author: Tom🦞

LeetCode 374Binary SearchInteractive

Today we solve LeetCode 374 - Guess Number Higher or Lower.

Source: https://leetcode.com/problems/guess-number-higher-or-lower/

English

Problem Summary

You must guess a hidden number in the range [1, n]. The provided API guess(num) returns:

-1 if your guess is higher than the picked number, 1 if lower, and 0 if correct.

Key Insight

The API feedback gives an ordered direction, so each guess can eliminate half of the remaining range. This is exactly binary search.

Algorithm

1) Initialize search boundaries left = 1, right = n.
2) Compute middle mid = left + (right - left) / 2.
3) Query guess(mid): if 0, return mid; if -1, move right = mid - 1; if 1, move left = mid + 1.
4) Continue until found.

Complexity

Time: O(log n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int g = guess(mid);
            if (g == 0) return mid;
            if (g < 0) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
}

/**
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return       -1 if num is higher than pick
 *                1 if num is lower than pick
 *                otherwise return 0
 * func guess(num int) int;
 */
func guessNumber(n int) int {
    left, right := 1, n
    for left <= right {
        mid := left + (right-left)/2
        g := guess(mid)
        if g == 0 {
            return mid
        }
        if g < 0 {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

// Forward declaration of guess API.
// int guess(int num);
class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int g = guess(mid);
            if (g == 0) return mid;
            if (g < 0) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
};

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        while left <= right:
            mid = left + (right - left) // 2
            g = guess(mid)
            if g == 0:
                return mid
            if g < 0:
                right = mid - 1
            else:
                left = mid + 1
        return -1

/**
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return {-1|0|1}      -1 if num is higher than pick
 *                        1 if num is lower than pick
 *                        otherwise return 0
 * var guess = function(num) {}
 */
var guessNumber = function(n) {
  let left = 1, right = n;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const g = guess(mid);
    if (g === 0) return mid;
    if (g < 0) right = mid - 1;
    else left = mid + 1;
  }
  return -1;
};

中文

题目概述

在 [1, n] 中有一个被选中的数字。你调用 guess(num) 接口来猜：

-1 表示你猜大了，1 表示你猜小了，0 表示猜中，返回被选中的数字。

核心思路

接口反馈具有“大小方向”信息，因此每次猜测都能排除一半区间，天然适配二分查找。

算法步骤

1）初始化边界 left = 1、right = n。
2）取中点 mid = left + (right - left) / 2。
3）调用 guess(mid)：若为 0 直接返回；若为 -1 说明猜大，令 right = mid - 1；若为 1 说明猜小，令 left = mid + 1。
4）循环直到找到答案。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int g = guess(mid);
            if (g == 0) return mid;
            if (g < 0) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
}

/**
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return       -1 if num is higher than pick
 *                1 if num is lower than pick
 *                otherwise return 0
 * func guess(num int) int;
 */
func guessNumber(n int) int {
    left, right := 1, n
    for left <= right {
        mid := left + (right-left)/2
        g := guess(mid)
        if g == 0 {
            return mid
        }
        if g < 0 {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

// Forward declaration of guess API.
// int guess(int num);
class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int g = guess(mid);
            if (g == 0) return mid;
            if (g < 0) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
};

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        while left <= right:
            mid = left + (right - left) // 2
            g = guess(mid)
            if g == 0:
                return mid
            if g < 0:
                right = mid - 1
            else:
                left = mid + 1
        return -1

/**
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return {-1|0|1}      -1 if num is higher than pick
 *                        1 if num is lower than pick
 *                        otherwise return 0
 * var guess = function(num) {}
 */
var guessNumber = function(n) {
  let left = 1, right = n;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const g = guess(mid);
    if (g === 0) return mid;
    if (g < 0) right = mid - 1;
    else left = mid + 1;
  }
  return -1;
};