LeetCode 374 Guess Number Higher or Lower 全解从二分查找 API 契约到多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读Guess Number Higher or LowerLeetCode 374是入门交互式二分查找的经典题目系统在[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 } }复杂度时间复杂度$O(n)$最坏情况需遍历整个区间空间复杂度$O(1)$仅使用常数个变量。3. 解法二二分搜索推荐直觉区间[1, n]有序guess返回的猜高/猜低/命中恰好构成三分支比较信号因此二分查找可以每轮把搜索空间缩小一半从 $O(n)$ 降至 $O(\log n)$。算法流程初始化两个指针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) // 猜低了向 [mid1, right] 收缩 } else { mid } } }// c/0374-guess-number-higher-or-lower.c long guess_bis(long min, long max){ long m (maxmin)/2; int tmp guess(m); if (tmp0) return m; else if (tmp0) return guess_bis(min,m-1); else return guess_bis(m1,max); } long guessNumber(long n){ return guess_bis(0,n); }从源码结构还可以看到两个值得注意的变体细节C 实现使用long并放宽下界为0guessNumber从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 选择不影响正确性。复杂度时间复杂度$O(\log n)$每轮将搜索空间减半空间复杂度$O(1)$迭代式递归式额外消耗 $O(\log n)$ 的调用栈但在 Rust/C 的尾递归风格下实际栈深可控。4. 解法三三分搜索直觉三分搜索把区间分成三段选取两个中点分别询问guess根据两组反馈一次排除三分之一或三分之二的空间。思路可行但它每一轮需要两次guessAPI 调用而二分每轮只需一次因此在本问题上三分并不比二分更快。算法流程初始化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 - 1guess(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; } } } }复杂度时间复杂度$O(\log_3 n)$但每轮需要两次guess调用常数因子更大空间复杂度$O(1)$。结论在本问题上三分搜索的理论轮数更少$\log_3 n \log_2 n$但每次迭代的 API 调用成本翻倍综合起来并不优于二分搜索。理解它主要是为了拓宽对按比例划分搜索空间这类思想的认知。5. 三种解法对比解法每轮 guess 调用次数时间复杂度空间复杂度适用场景线性搜索1$O(n)$$O(1)$仅用于理解题意或n极小二分搜索1$O(\log n)$$O(1)$最优方案推荐三分搜索2$O(\log_3 n)$$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 mid6.2 计算中点时的整数溢出直接写(l r) / 2当l与r都接近int上限例如n接近 $2^{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. 延伸阅读与仓库索引完整题解文档articles/guess-number-higher-or-lower.md解题进度总表README.md各语言源码实现python/0374-guess-number-higher-or-lower.pyjava/0374-guess-number-higher-or-lower.javacpp/0374-guess-number-higher-or-lower.cppjavascript/0374-guess-number-higher-or-lower.jscsharp/0374-guess-number-higher-or-lower.csgo/0374-guess-number-higher-or-lower.gokotlin/0374-guess-number-higher-or-lower.ktswift/0374-guess-number-higher-or-lower.swiftrust/0374-guess-number-higher-or-lower.rsc/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的防溢出写法与返回值方向记牢即可一通百通。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考