0278. First Bad Version¶
题目信息¶
- 题号:
0278
- 难度:
Easy
- 主题:
有序版本、单调布尔接口、边界查找
- 原题:
- 重点:
版本编号从 1 开始、坏版本一旦出现后续全部为坏、返回最早的坏版本并减少接口调用
题目重述¶
产品共有 n 个按发布时间排列的版本,编号为 1 到 n。其中某个版本是第一个坏版本,从它开始的所有后续版本也都是坏版本。平台提供 isBadVersion(version) 接口,用于查询指定版本是否为坏版本;实现函数并返回第一个坏版本的编号。
题目保证 1 <= firstBad <= n <= 2^31 - 1,因此至少存在一个坏版本。只能通过给定接口判断版本状态,不能直接访问隐藏的首个坏版本值。应尽量减少对 isBadVersion 的调用次数,返回值使用一基版本编号。
自建示例¶
坏版本位于后半段:
输入:n = 8,isBadVersion(1..5) = false,isBadVersion(6..8) = true
输出:6
解释:版本 6 是第一个返回 true 的版本,版本 1 到 5 都是好版本。
只有一个版本:
输入:n = 1,isBadVersion(1) = true
输出:1
解释:题目保证至少有一个坏版本,因此唯一版本就是第一个坏版本。
寻找第一个 true¶
把 isBadVersion 看成单调布尔序列:好版本为 false,从首个坏版本开始全部为 true。
在闭区间 [left,right] 内二分:
mid为坏版本时,首个坏版本不晚于mid,保留左半边并令right=mid;mid为好版本时,首个坏版本一定在右侧,令left=mid+1。
循环结束时 left==right,这个位置仍在候选区间内且是首个坏版本。中点计算使用
left + (right-left)/2,避免两个一基大编号相加时溢出。
正确性说明¶
循环不变量是:首个坏版本位于 [left,right]。坏中点不能被排除,因为它自己可能是首个;
好中点及其左侧都不可能是首个,只能排除。区间长度每轮严格减小,终止时唯一候选就是首个坏版本。
C++ 实现¶
// The judge provides isBadVersion(int version).
class Solution {
public:
int firstBadVersion(int n) {
long long left = 1;
long long right = n;
while (left < right) {
const long long middle = left + (right - left) / 2;
if (isBadVersion(static_cast<int>(middle))) {
right = middle;
} else {
left = middle + 1;
}
}
return static_cast<int>(left);
}
};
代码分析¶
每轮只调用一次接口并把候选区间缩小约一半,接口调用次数和时间复杂度为 O(log n),
额外空间为 O(1)。使用 long long 保存边界,避免在 n 接近 2^31-1 时中点表达式溢出;
题目保证至少存在一个坏版本,所以不需要处理“全为好版本”的额外返回值。