企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读

「猜数字大小」是 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维护当前搜索区间：

1. 初始化：left指向数字 $1$，right指向数字 $n$，区间为左闭右闭 $[left, right]$；
2. 计算中点：mid = left + (right - left) // 2；
3. 调用接口并收缩区间：
   • 若guess(mid) == 1：答案比mid大，令left = mid + 1；
   • 若guess(mid) == -1：答案比mid小，令right = mid - 1；
   • 若guess(mid) == 0：直接返回mid；
4. 循环直至命中或区间为空。

每一步都通过一次接口调用排除掉一半不可能包含答案的区间，这正是二分查找「减而治之」思想的体现。

参考代码

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 中进一步剖析了四类容易出错的细节。这些细节在本题的代码中均有对应体现：

由于本题采用「直接法」，三个分支（过大、过小、命中）一一对应接口的三种返回值，不需要像「排除法」那样在循环结束后额外判断nums[left]，因此实现非常直观，适合作为二分查找的入门练手题。

由浅入深：与仓库内同类题目的横向对比

对比 1：0378 第一个错误的版本

仓库题解 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。

对比 2：0375 猜数字大小 II（进阶预警）

仓库题解 docs/solutions/0300-0399/guess-number-higher-or-lower-ii.md 是本题的直接进阶版：猜错要按所猜数字支付现金，要求返回“确保获胜的最小现金数”。该题不能用二分查找求解——因为二分查找虽然能保证最少猜测次数，但最小猜测次数对应的支付金额并不是最小现金数，必须改用区间动态规划，时间复杂度 $O(n^3)$、空间复杂度 $O(n^2)$。这提醒我们：二分查找解决的是“最少比较次数”问题，而本题的变体引入了代价约束后，问题性质发生了根本变化。

总结与练习延伸

核心要点回顾

1. 读清交互语义：guess(num)返回 $1$ 表示答案更大、返回 $-1$ 表示答案更小，方向别搞反；
2. 识别二分前提：答案存在于有序整数区间 $[1, n]$，即使没有显式数组，二分查找同样适用——这是“隐式有序空间”二分的思想，后续很多题目（如求平方根、猜数字、查找插入位置）都会复用；
3. 掌握模板细节：左闭右闭区间 +mid = left + (right - left) // 2+left <= right循环 + 命中即返回，四要素齐备即可一次写对；
4. 复杂度意识：$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 两篇算法讲义，即可完成从原理到实战的完整闭环。

• 教程
• 文档
• 知识库