题目描述
思路解析
一句话答案：LeetCode 374 猜数字大小：1 到 n 里猜系统选的 pick，每问一次 guess 回偏大、偏小或命中。二分按反馈把候选区间减半，最少次数锁定 pick，时间 O(log n)、空间 O(1)。
只靠偏大偏小的回复，怎么锁定 pick
系统在 1 到 n 里偷偷选了一个数 pick。你能做的只有一件事：挑一个数 m 去问 guess(m)，它回 1 表示 m 比 pick 小（猜小了）、回 −1 表示 m 比 pick 大（猜大了）、回 0 表示命中。看不到答案、只能靠每次回复一点点逼近，这种方式叫交互反馈。题目要的不是随便猜中，而是用尽量少的次数问出 pick。
从 1 开始一个个问，为什么会被卡死
笨办法是从 1 挨个问：guess(1)、guess(2)、guess(3)……直到返回 0。一定能中，可 pick 若靠近 n 就得问将近 n 次，n 到十亿这条线性扫（从头一个个试）就慢得没法接受。更亏的是，guess 明明告诉了你「偏大还是偏小」，挨个问却只用「中没中」，方向信息全浪费。
偏大偏小这条回复，凭什么能砍掉一半
关键在于 1 到 n 本身从小到大排好。挑正中间的数 m 去问，guess 的回复直接圈定 pick 在哪半边：回 1 说明 pick 比 m 大，m 连同左边整段排除；回 −1 说明 pick 比 m 小，m 连同右边全排除。一问就砍掉一半候选，这正是二分查找（每问一次，候选就减半的找法）能用的前提。
区间怎么收、mid 怎么取才不会漏掉 pick
用 lo、hi 两头框住还没排除的候选，起初 lo=1、hi=n，闭区间 [lo, hi]（两端都算数）里自始至终含着 pick。每轮取中点 mid = lo + (hi − lo) // 2，问 guess(mid)：回 0 就返回 mid；回 1 说明 pick 更大，lo = mid + 1；回 −1 说明 pick 更小，hi = mid − 1。收缩必须 ±1——mid 已问过、不是答案，得跨过它，否则区间缩不动、一直空转。lo 超过 hi 时候选空了，循环停。
拿 n=10、pick=6 逐轮把区间夹到底
拿题面的 n=10、pick=6 走一遍。第一轮 lo=1、hi=10，mid = 1 + (10 − 1) // 2 = 5，guess(5) 返回 1（5 比 6 小），pick 在右半，lo 提到 6。第二轮 lo=6、hi=10，mid = 6 + (10 − 6) // 2 = 8，guess(8) 返回 −1（8 比 6 大），pick 在左半，hi 退到 7。第三轮 lo=6、hi=7，mid = 6 + (7 − 6) // 2 = 6，guess(6) 返回 0，命中返回 6。十个数只问 3 次就锁定，每轮都砍掉一半。
认反 guess 的方向，越问越偏
每问一次候选减半，最多约 log₂n 次收敛，时间 O(log n)；只用 lo、hi、mid 三个记号，空间 O(1)。最坑是 guess 方向记反：返回 1 是猜小了、该 lo = mid + 1，反着写越问越偏。收缩漏 ±1、写成 lo = mid，mid 不挪、循环卡死。mid 写 (lo+hi)//2 在 n 大时溢出，换 lo + (hi − lo) // 2 才稳；n=1 一问即中，两端值也照常收敛。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「取中点 mid → guess → 偏小 lo=mid+1、偏大 hi=mid−1、命中即停」,下面每帧都在套它。
还没被排除的范围是 [1, 12](灰格已排除)。取中点 mid = 6(用整除 (12−1)//2 向下取整:候选个数为奇数时正好是正中间,偶数时取靠左那个),下一步去问 guess(6)。
guess(6) 返回 1。返回 1 表示猜的数比 pick 小,也就是 pick 比 6 大,答案落在它右边。
既然 pick 比 6 大,1 到 6(含刚问过的 6)全部排除、标灰,lo 跳到 7。左半被砍掉,范围缩成 [7, 12]。
还没被排除的范围是 [7, 12](灰格已排除)。取中点 mid = 9(用整除 (12−7)//2 向下取整:候选个数为奇数时正好是正中间,偶数时取靠左那个),下一步去问 guess(9)。
guess(9) 返回 1。返回 1 表示猜的数比 pick 小,也就是 pick 比 9 大,答案落在它右边。
既然 pick 比 9 大,7 到 9(含刚问过的 9)全部排除、标灰,lo 跳到 10。左半被砍掉,范围缩成 [10, 12]。
还没被排除的范围是 [10, 12](灰格已排除)。取中点 mid = 11(用整除 (12−10)//2 向下取整:候选个数为奇数时正好是正中间,偶数时取靠左那个),下一步去问 guess(11)。
guess(11) 返回 -1。返回 −1 表示猜的数比 pick 大,也就是 pick 比 11 小,答案落在它左边。
既然 pick 比 11 小,11 到 12(含刚问过的 11)全部排除、标灰,hi 退到 10。右半被砍掉,范围缩成 [10, 10]。
还没被排除的范围是 [10, 10](灰格已排除)。取中点 mid = 10(用整除 (10−10)//2 向下取整:候选个数为奇数时正好是正中间,偶数时取靠左那个),下一步去问 guess(10)。
guess(10) 返回 0。正好等于 pick,猜中了!
10 就是 pick,绿色标出,二分结束。回头看,从 12 个数里只问了 4 次就锁定了它,每次都砍掉一半,这就是二分的威力。
边界:n=1、pick 在端点、一猜即中,都能正常处理。
面试考点:把 guess API 当成有序范围上的比较器,闭区间二分照搬。
参考代码
PICK = 1def guess(num: int) -> int: if num == PICK: return 0 return 1 if num < PICK else -1class Solution: def guessNumber(self, n: int) -> int: left, right = 1, n while left <= right: mid = left + (right - left) // 2 g = guess(mid) if g == 0: return mid if g > 0: left = mid + 1 else: right = mid - 1 return -1复杂度
- 时间：O(log n)，每问一次范围减半,最多约 ceil(log2(n+1)) 次就收敛,即 O(log n) 次
- 空间：O(1)，只用 left、right、mid 几个变量
易错点
面试追问把动画讲成自己的话
追问这题和普通「有序数组里二分找值」有什么区别?
追问为什么用闭区间 [left,right]、循环条件 left ≤ right?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二分查找
LeetCode 704 · 简单 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题