LeetCode 374 Guess Number Higher or Lower 全解:从二分查找 API 契约到多语言实现

原创2026-09-17 11:01:362,000 阅读
文章标签:示例工程教程

LeetCode 374 Guess Number Higher or Lower 全解:从二分查找 API 契约到多语言实现

导读

Guess Number Higher or Lower(LeetCode 374)是入门"交互式二分查找"的经典题目:系统在 <a href="https://link.gitcode.com/i/ca777f0df4eae50253a529f0d27cd7d4" target="_blank">1, n] 中悄悄选定一个数字,你只能通过 guess(num) 接口获得"猜高/猜低/命中"三类反馈来逼近答案。本文以 [articles/guess-number-higher-or-lower.md 为核心骨架,完整覆盖线性搜索、二分搜索、三分搜索三种解法的直觉、算法流程与复杂度分析,并结合本仓库 python/、java/、cpp/、go/、javascript/、kotlin/、swift/、rust/、csharp/、c/ 下 10 种语言的真实源码逐一对齐验证。读完你将掌握:如何正确理解 guess() 的返回值语义、二分边界收缩的两种写法(迭代/递归)、l + (r - l) / 2 防溢出的原理,以及为什么三分搜索在本问题上不占优。


1. 问题背景与 guess API 契约

题目要求:系统从 1 到 n 之间挑选一个数字,你需要猜出它。每轮你可以调用一次 guess(num),返回值语义如下(这是全题最容易踩坑的地方):

返回值 含义
-1 你猜的 num 高于被选中的数字(需要往小了猜)
1 你猜的 num 低于被选中的数字(需要往大了猜)
0 猜中,num 即答案

注意:返回值中的 -1/1 描述的是"你的猜测与答案的相对关系",而不是"答案相对你猜测的方向",两者恰好相反。所有语言实现顶部都带有相同的 API 注释,例如 cpp/0374-guess-number-higher-or-lower.cpp:

/**
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

该题在仓库 README.md 的解题进度表中被标记为 0374 - Guess Number Higher Or Lower,其中 C、C++、C#、Go、Java、JavaScript、Kotlin、Python、Swift、Rust 均已实现。

前置知识:二分查找

在动手前需要熟练掌握二分查找:在一个有序区间上,利用每次比较的反馈将搜索空间对半缩小。本题的搜索范围 [1, n] 天然有序,而 guess() 返回的"高/低/命中"反馈正是二分查找所需要的三分支比较信号,因此二分是本题的最优主解法。


2. 解法一:线性搜索

直觉

最朴素的思路是从 1 到 n 逐个尝试,调用 guess(num) 判断是否命中。它一定能找到答案,但当 n 很大时可能需要遍历全部数字,效率低下。

算法流程

  1. 遍历 1 到 n 的每一个数;
  2. 对每个数调用 guess API;
  3. 若返回 0,当前数即答案,返回之;
  4. 否则继续,直到找到答案。

多语言实现

Python / Java / C++ / JavaScript

# 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:
        for num in range(1, n + 1):
            if guess(num) == 0:
                return num
/**
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        for (int num = 1; num <= n; num++) {
            if (guess(num) == 0) return num;
        }
        return n;
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        for (int num = 1; num <= n; num++) {
            if (guess(num) == 0) return num;
        }
        return n;
    }
};
/**
 * Forward declaration of guess API.
 * @param {number} 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
 * function guess(num) {}
 */

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    guessNumber(n) {
        for (let num = 1; num <= n; num++) {
            if (guess(num) === 0) return num;
        }
        return n;
    }
}

C# / Go / Kotlin / Swift / Rust

/**
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

public class Solution : GuessGame {
    public int GuessNumber(int n) {
        for (int num = 1; num <= n; num++) {
            if (guess(num) == 0) return num;
        }
        return n;
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * func guess(num int) int;
 */

func guessNumber(n int) int {
    for num := 1; num <= n; num++ {
        if guess(num) == 0 {
            return num
        }
    }
    return n
}
/**
 * Forward declaration of guess API.
 * @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
 * fun guess(num: Int): Int {}
 */

class Solution : GuessGame() {
    override fun guessNumber(n: Int): Int {
        for (num in 1..n) {
            if (guess(num) == 0) return num
        }
        return n
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * func guess(_ num: Int) -> Int
 */

class Solution : GuessGame {
    func guessNumber(_ n: Int) -> Int {
        for num in 1...n {
            if guess(num) == 0 {
                return num
            }
        }
        return n
    }
}
// Forward declaration of guess API.
// unsafe fn guess(num: i32) -> i32;

impl Solution {
    unsafe fn guessNumber(n: i32) -> i32 {
        for num in 1..=n {
            if guess(num) == 0 {
                return num;
            }
        }
        n
    }
}

复杂度

  • 时间复杂度:O(n)O(n),最坏情况需遍历整个区间;
  • 空间复杂度:O(1)O(1),仅使用常数个变量。

3. 解法二:二分搜索(推荐)

直觉

区间 [1, n] 有序,guess 返回的"猜高/猜低/命中"恰好构成三分支比较信号,因此二分查找可以每轮把搜索空间缩小一半,从 O(n)O(n) 降至 O(log⁡n)O(\log n)。

算法流程

  1. 初始化两个指针 l = 1、r = n;
  2. 计算中点 m = l + (r - l) / 2(避免溢出,见下文"常见陷阱");
  3. 调用 guess(m):
    • 返回 0:命中,返回 m;
    • 返回 1(答案更大):令 l = m + 1;
    • 返回 -1(答案更小):令 r = m - 1;
  4. 重复直至找到答案。

多语言实现(迭代式)

Python / Java / C++ / JavaScript

# 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:
        l, r = 1, n
        while True:
            m = (l + r) // 2
            res = guess(m)
            if res > 0:
                l = m + 1
            elif res < 0:
                r = m - 1
            else:
                return m
/**
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int l = 1, r = n;
        while (true) {
            int m = l + (r - l) / 2;
            int res = guess(m);
            if (res > 0) {
                l = m + 1;
            } else if (res < 0) {
                r = m - 1;
            } else {
                return m;
            }
        }
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        int l = 1, r = n;
        while (true) {
            int m = l + (r - l) / 2;
            int res = guess(m);
            if (res > 0) {
                l = m + 1;
            } else if (res < 0) {
                r = m - 1;
            } else {
                return m;
            }
        }
    }
};
/**
 * Forward declaration of guess API.
 * @param {number} 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
 * function guess(num) {}
 */

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    guessNumber(n) {
        let l = 1,
            r = n;
        while (true) {
            let m = Math.floor((l + r) / 2);
            let res = guess(m);
            if (res > 0) {
                l = m + 1;
            } else if (res < 0) {
                r = m - 1;
            } else {
                return m;
            }
        }
    }
}

C# / Go / Kotlin / Swift / Rust

/**
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

public class Solution : GuessGame {
    public int GuessNumber(int n) {
        int l = 1, r = n;
        while (true) {
            int m = l + (r - l) / 2;
            int res = guess(m);
            if (res > 0) {
                l = m + 1;
            }
            else if (res < 0) {
                r = m - 1;
            }
            else {
                return m;
            }
        }
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * func guess(num int) int;
 */

func guessNumber(n int) int {
    l, r := 1, n
    for {
        m := l + (r-l)/2
        res := guess(m)
        if res > 0 {
            l = m + 1
        } else if res < 0 {
            r = m - 1
        } else {
            return m
        }
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * fun guess(num: Int): Int {}
 */

class Solution : GuessGame() {
    override fun guessNumber(n: Int): Int {
        var l = 1
        var r = n
        while (true) {
            val m = l + (r - l) / 2
            val res = guess(m)
            if (res > 0) {
                l = m + 1
            } else if (res < 0) {
                r = m - 1
            } else {
                return m
            }
        }
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * func guess(_ num: Int) -> Int
 */

class Solution : GuessGame {
    func guessNumber(_ n: Int) -> Int {
        var l = 1
        var r = n
        while true {
            let m = l + (r - l) / 2
            let res = guess(m)
            if res > 0 {
                l = m + 1
            } else if res < 0 {
                r = m - 1
            } else {
                return m
            }
        }
    }
}
// Forward declaration of guess API.
// unsafe fn guess(num: i32) -> i32;

impl Solution {
    unsafe fn guessNumber(n: i32) -> i32 {
        let (mut l, mut r) = (1, n);
        loop {
            let m = l + (r - l) / 2;
            let res = guess(m);
            if res > 0 {
                l = m + 1;
            } else if res < 0 {
                r = m - 1;
            } else {
                return m;
            }
        }
    }
}

仓库源码对照:迭代式与递归式

仓库中的实现与上述算法一一对应,并且同时提供了迭代与递归两种风格,值得对照阅读:

// rust/0374-guess-number-higher-or-lower.rs
impl Solution {
    unsafe fn guessNumber(n: i32) -> i32 {
        Self::binary_search(1, n)
    }

    unsafe fn binary_search(left: i32, right: i32) -> i32 {
        let mid = left + (right - left ) / 2;

        if guess(mid) < 0 {
            Self::binary_search(1, mid)      // 猜高了,向 [1, mid] 收缩
        } else if guess(mid) > 0 {
            Self::binary_search(mid + 1, right) // 猜低了,向 [mid+1, right] 收缩
        } else {
            mid
        }
    }
}
// c/0374-guess-number-higher-or-lower.c
long guess_bis(long min, long max){
    long m = (max+min)/2;
    int tmp = guess(m);
    if (tmp==0)
        return m;
    else if (tmp<0)
        return guess_bis(min,m-1);
    else
        return guess_bis(m+1,max);
}

long guessNumber(long n){
	return guess_bis(0,n);
}

从源码结构还可以看到两个值得注意的变体细节:

  1. C 实现使用 long 并放宽下界为 0:guessNumber 从 guess_bis(0, n) 出发,依靠 guess 反馈自动收敛到 [1, n] 内的正确答案,且用 long 避免 int 在极端输入下的溢出,属于"以更大类型换安全"的工程化写法;
  2. C# 实现采用 0-based 区间与位运算:left = 0, right = n - 1,中点用 left + ((right - left) >> 1)(见 csharp/0374-guess-number-higher-or-lower.cs)。>> 1 等价于除以 2,且对非负数来说移位与整除结果一致,代码风格上更贴近底层。由于题目保证答案必然存在于区间内,该写法最终通过 while (left <= right) 正常命中返回;若区间理论上有空的可能,则依赖 return left 兜底。

这两种变体都验证了一个核心事实:只要严格遵循 guess 的返回值语义(-1 收缩右界、1 收缩左界),区间起点的 0-based/1-based 选择不影响正确性。

复杂度

  • 时间复杂度:O(log⁡n)O(\log n),每轮将搜索空间减半;
  • 空间复杂度:O(1)O(1)(迭代式);递归式额外消耗 O(log⁡n)O(\log n) 的调用栈,但在 Rust/C 的尾递归风格下实际栈深可控。

4. 解法三:三分搜索

直觉

三分搜索把区间分成三段,选取两个中点分别询问 guess,根据两组反馈一次排除三分之一或三分之二的空间。思路可行,但它每一轮需要两次 guess API 调用,而二分每轮只需一次,因此在本问题上三分并不比二分更快。

算法流程

  1. 初始化 l = 1、r = n;
  2. 计算两个中点 m1 = l + (r - l) / 3、m2 = r - (r - l) / 3;
  3. 分别询问 guess(m1) 与 guess(m2):
    • 任一返回 0:返回该中点;
    • 两者之和为 0(一个 1、一个 -1):答案夹在 m1 与 m2 之间,令 l = m1 + 1、r = m2 - 1;
    • guess(m1) == -1:答案在 m1 左侧,令 r = m1 - 1;
    • 否则答案在 m2 右侧,令 l = m2 + 1;
  4. 重复直至找到答案。

多语言实现

Python / Java / C++ / JavaScript

# 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:
        l, r = 1, n
        while True:
            m1 = l + (r - l) // 3
            m2 = r - (r - l) // 3
            if guess(m1) == 0:
                return m1
            if guess(m2) == 0:
                return m2
            if guess(m1) + guess(m2) == 0:
                l = m1 + 1
                r = m2 - 1
            elif guess(m1) == -1:
                r = m1 - 1
            else:
                l = m2 + 1
/**
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int l = 1, r = n;
        while (true) {
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;
            if (guess(m1) == 0) return m1;
            if (guess(m2) == 0) return m2;
            if (guess(m1) + guess(m2) == 0) {
                l = m1 + 1;
                r = m2 - 1;
            } else if (guess(m1) == -1) {
                r = m1 - 1;
            } else {
                l = m2 + 1;
            }
        }
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        int l = 1, r = n;
        while (true) {
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;
            if (guess(m1) == 0) return m1;
            if (guess(m2) == 0) return m2;
            if (guess(m1) + guess(m2) == 0) {
                l = m1 + 1;
                r = m2 - 1;
            } else if (guess(m1) == -1) {
                r = m1 - 1;
            } else {
                l = m2 + 1;
            }
        }
    }
};
/**
 * Forward declaration of guess API.
 * @param {number} 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
 * function guess(num) {}
 */

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    guessNumber(n) {
        let l = 1,
            r = n;
        while (true) {
            let m1 = l + Math.floor((r - l) / 3);
            let m2 = r - Math.floor((r - l) / 3);
            if (guess(m1) === 0) return m1;
            if (guess(m2) === 0) return m2;
            if (guess(m1) + guess(m2) === 0) {
                l = m1 + 1;
                r = m2 - 1;
            } else if (guess(m1) === -1) {
                r = m1 - 1;
            } else {
                l = m2 + 1;
            }
        }
    }
}

C# / Go / Kotlin / Swift / Rust

/**
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

public class Solution : GuessGame {
    public int GuessNumber(int n) {
        int l = 1, r = n;
        while (true) {
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;

            if (guess(m1) == 0) return m1;
            if (guess(m2) == 0) return m2;

            if (guess(m1) + guess(m2) == 0) {
                l = m1 + 1;
                r = m2 - 1;
            }
            else if (guess(m1) == -1) {
                r = m1 - 1;
            }
            else {
                l = m2 + 1;
            }
        }
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * func guess(num int) int;
 */

func guessNumber(n int) int {
    l, r := 1, n
    for {
        m1 := l + (r-l)/3
        m2 := r - (r-l)/3
        if guess(m1) == 0 {
            return m1
        }
        if guess(m2) == 0 {
            return m2
        }
        if guess(m1)+guess(m2) == 0 {
            l = m1 + 1
            r = m2 - 1
        } else if guess(m1) == -1 {
            r = m1 - 1
        } else {
            l = m2 + 1
        }
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * fun guess(num: Int): Int {}
 */

class Solution : GuessGame() {
    override fun guessNumber(n: Int): Int {
        var l = 1
        var r = n
        while (true) {
            val m1 = l + (r - l) / 3
            val m2 = r - (r - l) / 3
            if (guess(m1) == 0) return m1
            if (guess(m2) == 0) return m2
            if (guess(m1) + guess(m2) == 0) {
                l = m1 + 1
                r = m2 - 1
            } else if (guess(m1) == -1) {
                r = m1 - 1
            } else {
                l = m2 + 1
            }
        }
    }
}
/**
 * Forward declaration of guess API.
 * @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
 * func guess(_ num: Int) -> Int
 */

class Solution : GuessGame {
    func guessNumber(_ n: Int) -> Int {
        var l = 1
        var r = n
        while true {
            let m1 = l + (r - l) / 3
            let m2 = r - (r - l) / 3
            if guess(m1) == 0 { return m1 }
            if guess(m2) == 0 { return m2 }
            if guess(m1) + guess(m2) == 0 {
                l = m1 + 1
                r = m2 - 1
            } else if guess(m1) == -1 {
                r = m1 - 1
            } else {
                l = m2 + 1
            }
        }
    }
}
// Forward declaration of guess API.
// unsafe fn guess(num: i32) -> i32;

impl Solution {
    unsafe fn guessNumber(n: i32) -> i32 {
        let (mut l, mut r) = (1, n);
        loop {
            let m1 = l + (r - l) / 3;
            let m2 = r - (r - l) / 3;
            if guess(m1) == 0 { return m1; }
            if guess(m2) == 0 { return m2; }
            if guess(m1) + guess(m2) == 0 {
                l = m1 + 1;
                r = m2 - 1;
            } else if guess(m1) == -1 {
                r = m1 - 1;
            } else {
                l = m2 + 1;
            }
        }
    }
}

复杂度

  • 时间复杂度:O(log⁡3n)O(\log_3 n),但每轮需要两次 guess 调用,常数因子更大;
  • 空间复杂度:O(1)O(1)。

结论:在本问题上三分搜索的理论轮数更少(log⁡3n<log⁡2n\log_3 n < \log_2 n),但每次迭代的 API 调用成本翻倍,综合起来并不优于二分搜索。理解它主要是为了拓宽对"按比例划分搜索空间"这类思想的认知。


5. 三种解法对比

解法 每轮 guess 调用次数 时间复杂度 空间复杂度 适用场景
线性搜索 1 O(n)O(n) O(1)O(1) 仅用于理解题意或 n 极小
二分搜索 1 O(log⁡n)O(\log n) O(1)O(1) 最优方案,推荐
三分搜索 2 O(log⁡3n)O(\log_3 n) O(1)O(1) 理论拓展,实际不占优

6. 常见陷阱

6.1 误解 guess() 的返回值方向

guess() 返回 -1 表示你的猜测高于答案,返回 1 表示你的猜测低于答案。这与直觉相反——很多人默认"正数表示往高了走",一旦把两个分支写反,二分边界就会朝错误方向收缩,导致死循环或返回错误结果。

对照仓库实现可以更直观地确认正确写法(以 python/0374-guess-number-higher-or-lower.py 为例):

class Solution:
    def guessNumber(self, n: int) -> int:
        low = 1
        high = n
        while True:
            mid = low + (high - low) // 2
            myGuess = guess(mid)
            if myGuess == 1:        # 猜低了,答案在右侧
                low = mid + 1
            elif myGuess == -1:     # 猜高了,答案在左侧
                high = mid - 1
            else:
                return mid

6.2 计算中点时的整数溢出

直接写 (l + r) / 2,当 l 与 r 都接近 int 上限(例如 n 接近 231−12^{31}-1)时,l + r 会溢出为负数,导致中点计算错误。安全写法是:

m = l + (r - l) / 2

它先求区间长度再与左端点相加,规避了两个大数相加。在 Java、C++、Go、C#、Rust 等固定位宽整数语言中这是必须养成的习惯。本仓库的绝大多数实现(如 java/0374-guess-number-higher-or-lower.java、go/0374-guess-number-higher-or-lower.go、rust/0374-guess-number-higher-or-lower.rs)都统一采用了 l + (r - l) / 2 写法;C 实现则通过 long 类型天然规避该问题;C# 实现用位运算 left + ((right - left) >> 1) 达到了同样的防溢出效果。


7. 延伸阅读与仓库索引

掌握本题后,guess 这种"黑盒比较器 + 三分支反馈"的交互模式会反复出现在"二分答案"类问题中(如 articles/eating-bananas.md、articles/koko-eating-bananas.md),把 l + (r - l) / 2 的防溢出写法与返回值方向记牢,即可一通百通。

登录后查看全文
leetcode