LeetCode 278. 第一个错误的版本
题目描述
题意分析
版本编号为
1..n，从第一个错误版本开始，后面的版本全部错误。只能通过isBadVersion(version)查询某个版本是否错误，需要尽量减少查询次数，找出错误区间的起点。查询结果按版本号排列一定是“若干个
false，接着全是true”，因此要找的是第一个true，不是任意一个错误版本。题目保证至少有一个错误版本，答案一定在[1,n]中。
解法：二分查找判定答案
核心思路
[!blue]
用闭区间
[left,right]保存第一个错误版本的候选范围，始终保证真正答案没有被排除。每轮只查询中点mid，根据结果一次排除约一半候选。若
isBadVersion(mid)为真，第一个错误版本只能在mid或其左侧；由于mid自己仍可能是答案，应令right = mid。若结果为假，mid及其左侧版本都正确，答案只能在右侧，应令left = mid+1。当
left < right时，向下取整的中点满足left <= mid < right，两种更新都能严格缩小区间，同时保留答案。直到两端相等，区间只剩唯一候选，直接返回它即可，无需再调用接口确认。
n可以接近 32 位整数上限，中点使用left + (right-left)/2，避免直接相加越界。版本从1开始，整个过程也不会查询不存在的第0个版本。
解题步骤
- 初始化
left = 1、right = n。- 只要
left < right，计算下中点并调用一次isBadVersion(mid)。- 中点错误就保留它作为右边界；中点正确就把左边界移到
mid+1。- 返回最终的
left。当n == 1时，题目保证唯一版本错误，循环无需执行。
代码实现
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1;
int right = n;
// 区间内始终保留第一个错误版本这个答案。
while (left < right) {
int mid = left + (right - left) / 2;
// 坏中点仍可能是首个，右边界保留它
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
func firstBadVersion(n int) int {
// 用二分查找第一个满足 isBadVersion 的位置。
left, right := 1, n
for left < right {
mid := left + (right-left)/2
// 坏中点仍可能是首个，右边界保留它
if isBadVersion(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
复杂度分析
- 时间复杂度：$O(\log(n+1))$，接口调用次数不超过
ceil(log2 n)，并非每次都恰好用满。- 空间复杂度：$O(1)$，二分边界。
关键点总结
[!green]
- 二分能成立的依据是错误状态的单调性，每次查询都能排除一整段版本。
- 中点错误时保留，中点正确时排除；两种边界更新来自同一个“答案仍在闭区间内”的不变量。
- 返回收敛后的边界，最后查询的中点不一定就是答案。
易错点总结
[!yellow]
- 中点错误时写成
right = mid-1：会把可能正是首个错误版本的mid一起排除。- 左端仍取好中点，两候选时无法前进。
- 单点仍进入循环且右端保留中点，会一直重复。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 35. 搜索插入位置 | 简单 | 同样查找从false到true的第一个位置，本题判定由isBadVersion接口提供。 |
| 704. 二分查找 | 简单 | 都使用二分缩小范围，但本题寻找单调边界，不是与某个固定数值比较相等。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！