题目描述
思路解析动画文字版
记住「取中点 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题