题目描述
思路解析动画文字版
下面 15 步动画会按主解代码推进,而不是泛泛讲题型。
1. 读入版本:6 个版本,关键性质:版本好坏是单调的——一旦某版本坏了,它之后全坏。所以存在一个分界点,二分就是找它。本例第一个坏的是 5。
2. 初始化 l, r:二分边界 l=1、r=6。第一个坏版本一定落在区间 [1,6] 里,当前 6 个候选。
3. 第1轮 · 取中点:取中点 mid=(1+6)//2=3,准备检查版本 3。
4. 第1轮 · 测好坏:调用 isBad(3) 返回 False,版本 3 是好的。
5. 第1轮 · 收缩:版本 3 好,第一个坏的在它右边,l=mid+1=4。版本 1~3 排除(变灰)。
6. 区间减半:一次检查就排掉了一半候选:从 6 个缩到 3 个,搜索区间变成 [4,6]。这正是二分 O(log n) 的来源。
7. 第2轮 · 取中点:区间 [4,6]。mid=(4+6)//2=5,检查版本 5。
8. 第2轮 · 测好坏:isBad(5) 返回 True,版本 5 是坏的。
9. 第2轮 · 收缩:版本 5 坏,它可能就是第一个坏的,保留它,r=mid=5(不是 mid-1)。版本 6 排除。
10. 区间再减半:候选再减到 2 个:[4,5]。每轮都把范围砍一半,逼近分界点。
11. 第3轮 · 取中点:区间 [4,5]。mid=(4+5)//2=4,检查版本 4。
12. 第3轮 · 测好坏:isBad(4) 返回 False,版本 4 是好的。
13. 第3轮 · 收缩:版本 4 好,l=mid+1=5,版本 4 排除。
14. 区间收成一点:l 与 r 撞在版本 5,区间只剩一个点,循环条件 l 小于 r 不再成立,退出。
15. 返回 5:返回 5。第一个错误版本就是 5。6 个版本只用 3 次检查,时间 O(log n)。
记住这题的代码骨架:题意约束先落到状态变量,再用循环或递归维护它。
参考代码
class Solution: def firstBadVersion(self, n): l = 1 r = n while l < r: mid = (l + r) // 2 if isBadVersion(mid): r = mid else: l = mid + 1 return l复杂度
- 时间复杂度:O(log n),每次缩半
- 空间复杂度:O(1),只用边界
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
有效的完全平方数
LeetCode 367 · 简单 · 沿着 二分套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题