LeetCode 374 Guess Number Higher or Lower 全解:从二分查找 API 契约到多语言实现
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到n的每一个数; - 对每个数调用
guessAPI; - 若返回
0,当前数即答案,返回之; - 否则继续,直到找到答案。
多语言实现
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
}
}
复杂度
- 时间复杂度:,最坏情况需遍历整个区间;
- 空间复杂度:,仅使用常数个变量。
3. 解法二:二分搜索(推荐)
直觉
区间 [1, n] 有序,guess 返回的"猜高/猜低/命中"恰好构成三分支比较信号,因此二分查找可以每轮把搜索空间缩小一半,从 降至 。
算法流程
- 初始化两个指针
l = 1、r = n; - 计算中点
m = l + (r - l) / 2(避免溢出,见下文"常见陷阱"); - 调用
guess(m):- 返回
0:命中,返回m; - 返回
1(答案更大):令l = m + 1; - 返回
-1(答案更小):令r = m - 1;
- 返回
- 重复直至找到答案。
多语言实现(迭代式)
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;
}
}
}
}
仓库源码对照:迭代式与递归式
仓库中的实现与上述算法一一对应,并且同时提供了迭代与递归两种风格,值得对照阅读:
- 迭代式:以
low/high(或l/r)双指针在循环内收缩边界,例如 python/0374-guess-number-higher-or-lower.py、java/0374-guess-number-higher-or-lower.java、cpp/0374-guess-number-higher-or-lower.cpp、go/0374-guess-number-higher-or-lower.go、javascript/0374-guess-number-higher-or-lower.js、kotlin/0374-guess-number-higher-or-lower.kt、swift/0374-guess-number-higher-or-lower.swift; - 递归式:Rust 与 C 实现把"边界收缩"转化为递归调用,天然符合二分查找"分而治之"的语义:
// 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);
}
从源码结构还可以看到两个值得注意的变体细节:
- C 实现使用
long并放宽下界为0:guessNumber从guess_bis(0, n)出发,依靠guess反馈自动收敛到[1, n]内的正确答案,且用long避免int在极端输入下的溢出,属于"以更大类型换安全"的工程化写法; - 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 选择不影响正确性。
复杂度
- 时间复杂度:,每轮将搜索空间减半;
- 空间复杂度:(迭代式);递归式额外消耗 的调用栈,但在 Rust/C 的尾递归风格下实际栈深可控。
4. 解法三:三分搜索
直觉
三分搜索把区间分成三段,选取两个中点分别询问 guess,根据两组反馈一次排除三分之一或三分之二的空间。思路可行,但它每一轮需要两次 guess API 调用,而二分每轮只需一次,因此在本问题上三分并不比二分更快。
算法流程
- 初始化
l = 1、r = n; - 计算两个中点
m1 = l + (r - l) / 3、m2 = r - (r - l) / 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;
- 任一返回
- 重复直至找到答案。
多语言实现
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;
}
}
}
}
复杂度
- 时间复杂度:,但每轮需要两次
guess调用,常数因子更大; - 空间复杂度:。
结论:在本问题上三分搜索的理论轮数更少(),但每次迭代的 API 调用成本翻倍,综合起来并不优于二分搜索。理解它主要是为了拓宽对"按比例划分搜索空间"这类思想的认知。
5. 三种解法对比
| 解法 | 每轮 guess 调用次数 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 线性搜索 | 1 | 仅用于理解题意或 n 极小 |
||
| 二分搜索 | 1 | 最优方案,推荐 | ||
| 三分搜索 | 2 | 理论拓展,实际不占优 |
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 接近 )时,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. 延伸阅读与仓库索引
- 完整题解文档:articles/guess-number-higher-or-lower.md
- 解题进度总表:README.md
- 各语言源码实现:
- python/0374-guess-number-higher-or-lower.py
- java/0374-guess-number-higher-or-lower.java
- cpp/0374-guess-number-higher-or-lower.cpp
- javascript/0374-guess-number-higher-or-lower.js
- csharp/0374-guess-number-higher-or-lower.cs
- go/0374-guess-number-higher-or-lower.go
- kotlin/0374-guess-number-higher-or-lower.kt
- swift/0374-guess-number-higher-or-lower.swift
- rust/0374-guess-number-higher-or-lower.rs
- c/0374-guess-number-higher-or-lower.c
- 二分查找相关题解可进一步参考:articles/binary-search.md、articles/first-bad-version.md、articles/search-insert-position.md
掌握本题后,guess 这种"黑盒比较器 + 三分支反馈"的交互模式会反复出现在"二分答案"类问题中(如 articles/eating-bananas.md、articles/koko-eating-bananas.md),把 l + (r - l) / 2 的防溢出写法与返回值方向记牢,即可一通百通。