题目描述
思路解析
一句话答案：LeetCode 278 第一个错误的版本：版本是「好…好坏…坏」的单调序列，二分找第一个坏的位置。mid 坏就 r=mid 保住候选、好就 l=mid+1，每次砍半把调用从 O(n) 压到 O(log n)、空间 O(1)。
第一个错误的版本这道题在找什么
有 n 个版本，编号 1 到 n，从某个版本起坏，且一旦坏就之后全坏。你只有一个接口 isBadVersion(v)，问它第 v 版坏没坏、坏就返回 true。要找出第一个坏版本的编号，且调用次数尽量少。题面例子：n=5、第 4 版起坏，答案是 4。
为什么从头一个个问会太慢
从版本 1 挨个问 isBadVersion(1)、isBadVersion(2)……问到第一个返回 true 就停，能找到，但最坏要问将近 n 次；n 是十亿就得问接近十亿次，等不起。根子是没用上「一旦坏则之后全坏」这个结构——版本排得很有规律，逐个扫却当它杂乱一堆。
为什么这道题能二分
「一旦坏则之后全坏」意味着版本前一段全好、后一段全坏，中间只翻一次脸：「好好好坏坏坏」。isBadVersion 的返回值也从 false 变成 true、只翻这一次，是一条 false…false true…true 的分界。找第一个坏版本，就是找这条分界上第一个 true 的位置（这类『找第一个满足条件的下标』叫 lower_bound）。有这种单调（一个方向到底、不回头）结构，就能二分查找，不必逐格看。
mid 坏往哪边收、mid 好往哪边收
候选区间 [l, r]，l 左边界、r 右边界，第一个坏版本一定夹在中间。每轮取中点 mid（区间正中那个编号，取 l+(r-l)//2），只问一次 isBadVersion(mid)。它坏：答案是 mid 或在它左边，右边界收到 r = mid——是 mid 不是 mid-1，mid 自己可能就是答案、减一会丢掉它。它好：答案在 mid 右边，mid 连同左边全排除，l 推到 mid+1。答案始终在 [l, r] 内，循环到 l 和 r 撞在一起就是答案。
n=5、第 4 版起坏，逐问缩区间
版本坏好是「好好好坏坏」，l=1、r=5。第一轮 mid = 1+(5-1)//2 = 3，问 isBadVersion(3)，版本 3 好，于是 l = 3+1 = 4。第二轮区间剩 [4, 5]，mid = 4+(5-4)//2 = 4，问 isBadVersion(4)，版本 4 坏，于是 r = 4。此时 l、r 都等于 4，循环停下，返回 4。整趟只问了 2 次 isBadVersion。
右界多减一，就吞掉第一个坏版本
mid 坏说明答案在 mid 或更左，写成 r = mid-1 就等于断定 mid 不是答案、把它踢出区间，真答案恰是 mid 时就返回成它右边那个，错。好版本那支 l 必须是 mid+1，漏了加一、让 l 停在 mid，好版本还赖在区间里，区间永远缩不动，直接死循环。还有 mid 一律用 l+(r-l)//2，别写 (l+r)//2，l、r 接近整型上限时相加会溢出。这三处对了，每问一次砍掉一半候选，次数就是 O(log n)，n=10 亿也不过约 30 次；只用 l、r、mid 三个变量，空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
两条规则记牢：mid 坏 → r = mid（答案可能就是它，不能丢）；mid 好 → l = mid+1（它和它左边全排除）。区间每轮砍半，撞到一起就是答案。
第一遍：第 9 版起坏。一开始谁坏谁好都不知道，候选区间是全部 13 个版本，左边界 l 在版本 1、右边界 r 在版本 13。
取区间正中间：mid 落在版本 7。调用 isBadVersion(7)，问问它坏没坏——这是这一轮唯一的一次提问。
版本 7 是好的（标绿）。第一个坏版本一定在它右边，连它带左边一起排除，左边界推到下一格：l = mid + 1。
取区间正中间：mid 落在版本 10。调用 isBadVersion(10)，问问它坏没坏——这是这一轮唯一的一次提问。
版本 10 是坏的（标红）。第一个坏版本要么就是它、要么在它更左边，所以右边界收到这里：r = mid。它右边那些更不用看了。
取区间正中间：mid 落在版本 9。调用 isBadVersion(9)，问问它坏没坏——这是这一轮唯一的一次提问。
版本 9 是坏的（标红）。第一个坏版本要么就是它、要么在它更左边，所以右边界收到这里：r = mid。它右边那些更不用看了。
取区间正中间：mid 落在版本 8。调用 isBadVersion(8)，问问它坏没坏——这是这一轮唯一的一次提问。
版本 8 是好的（标绿）。第一个坏版本一定在它右边，连它带左边一起排除，左边界推到下一格：l = mid + 1。
l 和 r 撞到同一格，区间只剩一个候选——它就是第一个坏版本：版本 9。整轮只问了几次就锁定，远少于一个个试。
第二遍：第 4 版起坏（换个答案再走一遍）。一开始谁坏谁好都不知道，候选区间是全部 13 个版本，左边界 l 在版本 1、右边界 r 在版本 13。
取区间正中间：mid 落在版本 7。调用 isBadVersion(7)，问问它坏没坏——这是这一轮唯一的一次提问。
版本 7 是坏的（标红）。第一个坏版本要么就是它、要么在它更左边，所以右边界收到这里：r = mid。它右边那些更不用看了。
取区间正中间：mid 落在版本 4。调用 isBadVersion(4)，问问它坏没坏——这是这一轮唯一的一次提问。
版本 4 是坏的（标红）。第一个坏版本要么就是它、要么在它更左边，所以右边界收到这里：r = mid。它右边那些更不用看了。
取区间正中间：mid 落在版本 2。调用 isBadVersion(2)，问问它坏没坏——这是这一轮唯一的一次提问。
版本 2 是好的（标绿）。第一个坏版本一定在它右边，连它带左边一起排除，左边界推到下一格：l = mid + 1。
取区间正中间：mid 落在版本 3。调用 isBadVersion(3)，问问它坏没坏——这是这一轮唯一的一次提问。
版本 3 是好的（标绿）。第一个坏版本一定在它右边，连它带左边一起排除，左边界推到下一格：l = mid + 1。
l 和 r 撞到同一格，区间只剩一个候选——它就是第一个坏版本：版本 4。整轮只问了几次就锁定，远少于一个个试。
三个高频追问：能二分的前提（单调）、循环条件配 r=mid 的选择、调用次数 O(log n)。
参考代码
def firstBadVersion(n): l, r = 1, n # 候选区间 [l, r] while l < r: mid = l + (r - l) // 2 # 防溢出的取中点 if isBadVersion(mid): # mid 坏：答案在它或它左边 r = mid # 不能丢掉 mid，所以是 mid 不是 mid-1 else: # mid 好：答案在它右边 l = mid + 1 return l # l == r 时即第一个坏版本复杂度
- 时间：O(log n)，每轮把候选区间砍一半，最多问 log₂n 次就收敛
- 空间：O(1)，只用 l、r、mid 三个变量，不开额外空间
易错点
面试追问把动画讲成自己的话
追问为什么这题能用二分？
追问循环条件用 while (l < r) 还是 while (l <= r)？
追问调用 isBadVersion 的次数大概是多少？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
两个数组的交集 II
LeetCode 350 · 简单 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题