教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读「猜数字大小」是 LeetCode 0374 号简单题也是《算法通关手册》二分查找分类下的典型入门题题目不直接给你有序数组而是通过一个交互接口guess()提供每次猜测的反馈要求你在 $1 \sim n$ 的连续整数区间内定位被选中的数字 $x$。本文以该题为骨架完整讲解交互式二分查找的题面语义、直接法实现、复杂度分析、边界细节并结合本仓库的二分查找系列教程与同类题目给出可复制、可运行的完整解法与进阶对比。题目概述猜数字游戏的交互规则题面大意猜数字游戏规则如下给定一个整数 $n$题目会从 $1 \sim n$ 中随机选取一个整数 $x$。我们只能通过调用预置接口guess(num)来判断自己猜测的数字是否正确要求最终返回题目选取的数字 $x$。示例 1输入n 10, pick 6 输出6示例 2输入n 1, pick 1 输出1接口返回值语义必须吃透本题的唯一“数据结构”就是交互接口其返回值决定了二分查找的收缩方向务必准确理解返回 $-1$我选出的数字比你猜的数字小即pick num说明猜测过大答案在左半区间返回 $1$我选出的数字比你猜的数字大即pick num说明猜测过小答案在右半区间返回 $0$我选出的数字和你猜的数字一样即pick num恭喜猜中直接返回该数字。注意返回值方向容易混淆guess(num)返回 $1$ 代表“真实值比猜测值更大”此时应当向右搜索返回 $-1$ 则向左搜索。这与普通二分查找中“数组元素与目标值比较”的直觉相反做题时建议先写注释再编码。思路 1二分查找直接法解题思路题目要求返回被选中的数字 $x$而 $x$ 一定位于有序的整数区间 $[1, n]$ 内天然满足二分查找的“有序数据”前提。我们利用两个指针left、right维护当前搜索区间初始化left指向数字 $1$right指向数字 $n$区间为左闭右闭 $[left, right]$计算中点mid left (right - left) // 2调用接口并收缩区间若guess(mid) 1答案比mid大令left mid 1若guess(mid) -1答案比mid小令right mid - 1若guess(mid) 0直接返回mid循环直至命中或区间为空。每一步都通过一次接口调用排除掉一半不可能包含答案的区间这正是二分查找「减而治之」思想的体现。参考代码class Solution: def guessNumber(self, n: int) - int: left 1 right n while left right: mid left (right - left) // 2 ans guess(mid) if ans 1: left mid 1 elif ans -1: right mid - 1 else: return mid return 0代码要点说明mid left (right - left) // 2与(left right) // 2等价但通过减法避免了整型溢出风险Python 不会溢出其他语言可能本仓库的二分查找教程在 docs/01_array/01_14_array_binary_search_02.md 中明确推荐此写法循环条件left right对应「直接法」一旦命中立即返回循环退出则说明区间已空函数末尾的return 0在正常逻辑下不可达题目保证答案存在仅作兜底。复杂度分析时间复杂度$O(\log n)$。每轮调用一次guess接口区间规模减半至多执行 $\lceil \log_2 n \rceil$ 轮空间复杂度$O(1)$。仅使用left、right、mid等常数个变量。作为对照线性扫描逐个调用接口需要 $O(n)$ 次而二分查找将接口调用次数压缩到对数级——这与本仓库 docs/00_preface/00_03_algorithm_complexity.md 中“每次操作将问题规模缩小一半的算法时间复杂度为 $O(\log n)$”的论述完全一致。二分查找细节在本题中的体现本仓库在 docs/01_array/01_13_array_binary_search_01.md 中系统讲解了二分查找的基本思想与步骤在 docs/01_array/01_14_array_binary_search_02.md 中进一步剖析了四类容易出错的细节。这些细节在本题的代码中均有对应体现细节维度本题采用说明区间开闭左闭右闭[left, right]初始化left 1、right n逻辑最简单、最不易出错mid 计算left (right - left) // 2等价于向下取整求中点且防止溢出循环条件left right直接法写法命中即返回退出循环即区间为空区间收缩left mid 1/right mid - 1明确排除掉mid本身保证每次循环区间严格收缩由于本题采用「直接法」三个分支过大、过小、命中一一对应接口的三种返回值不需要像「排除法」那样在循环结束后额外判断nums[left]因此实现非常直观适合作为二分查找的入门练手题。由浅入深与仓库内同类题目的横向对比对比 10378 第一个错误的版本仓库题解 docs/solutions/0200-0299/first-bad-version.md 是二分查找的另一个经典交互场景接口isBadVersion(version)返回布尔值版本从「全好」到「全坏」存在单调性分界要求找到第一个坏版本。其实现采用「排除法」class Solution: def firstBadVersion(self, n): left 1 right n while left right: mid (left right) // 2 if isBadVersion(mid): right mid else: left mid 1 return left对比两者可以发现二分查找的两种主流模板直接法本题循环条件left right三分支命中立即返回适合答案性质简单、元素互不重复的场景排除法0378循环条件left right每轮排除不可能区间循环结束时left right返回left适合查找“边界”这类复杂场景。两种模板的详细原理与防死循环技巧如出现left mid时 mid 需向上取整可参见 docs/01_array/01_14_array_binary_search_02.md。对比 20375 猜数字大小 II进阶预警仓库题解 docs/solutions/0300-0399/guess-number-higher-or-lower-ii.md 是本题的直接进阶版猜错要按所猜数字支付现金要求返回“确保获胜的最小现金数”。该题不能用二分查找求解——因为二分查找虽然能保证最少猜测次数但最小猜测次数对应的支付金额并不是最小现金数必须改用区间动态规划时间复杂度 $O(n^3)$、空间复杂度 $O(n^2)$。这提醒我们二分查找解决的是“最少比较次数”问题而本题的变体引入了代价约束后问题性质发生了根本变化。总结与练习延伸核心要点回顾读清交互语义guess(num)返回 $1$ 表示答案更大、返回 $-1$ 表示答案更小方向别搞反识别二分前提答案存在于有序整数区间 $[1, n]$即使没有显式数组二分查找同样适用——这是“隐式有序空间”二分的思想后续很多题目如求平方根、猜数字、查找插入位置都会复用掌握模板细节左闭右闭区间 mid left (right - left) // 2left right循环 命中即返回四要素齐备即可一次写对复杂度意识$O(\log n)$ 时间、$O(1)$ 空间接口调用次数从 $O(n)$ 降至 $O(\log n)$。配套练习建议二分查找基础0704 二分查找见 docs/00_preface/00_05_solutions_list.md 题解总表交互式二分0278 第一个错误的版本查找插入位置0035 搜索插入位置边界类二分0034 在排序数组中查找元素的第一个和最后一个位置。完整二分查找题单可在 docs/00_preface/00_06_categories_list.md 的“二分查找题目”分类中检索配合 docs/01_array/01_13_array_binary_search_01.md 与 docs/01_array/01_14_array_binary_search_02.md 两篇算法讲义即可完成从原理到实战的完整闭环。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0270「最接近的二叉搜索树值」二分查找解法全解析AlgoNote 算法通关手册LeetCode 0270「最接近的二叉搜索树值」二分查找解法全解析 导读 本文基于 AlgoNote 开源算法学习仓库中的题解教程文档知识库AlgoNote「算法通关手册」题解搜索二维矩阵LeetCode 0074——对角线分治与二分查找AlgoNote「算法通关手册」题解搜索二维矩阵LeetCode 0074——对角线分治与二分查找 本篇是 AlgoNote「算法通关手册」针对力扣Le教程文档知识库AlgoNote 算法通关手册LeetCode 0167 两数之和 II——输入有序数组的双指针与二分查找解法全解析AlgoNote 算法通关手册LeetCode 0167 两数之和 II——输入有序数组的双指针与二分查找解法全解析 本文是「算法通关手册AlgoNote教程文档知识库上一篇mflux vs 原版FLUX性能对比与本地部署优势分析下一篇SwiftUI与Swift语言新特性eul中的现代Swift实践创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考