278. 第一个错误的版本
题目描述
某产品发布了 n 个版本，编号依次为 1 到 n。每个版本都在前一个版本的基础上开发，所以一旦某个版本出了问题，它后面的版本也全都有问题。
你可以调用接口 bool isBadVersion(version) 来查询编号为 version 的版本是否有问题。请写一个函数，输入 n，返回第一个出问题的版本号。调用接口的次数要尽量少。
测试数据中的 bad 就是答案，它只用来模拟接口的结果，你的函数拿不到它。
示例 1
输入：n = 5, bad = 4 输出：4
解释：isBadVersion(3) 为 false，isBadVersion(4) 为 true，所以第一个坏版本是 4。
示例 2
输入：n = 1, bad = 1 输出：1
解释：只有一个版本，并且它是坏的。
数据范围
1 <= bad <= n <= 2^31 - 1
解题思路
版本的好坏是“前面全好、后面全坏”，天然单调。在 [lo, hi] 中间打一次接口：mid 是坏的，第一个坏版本不会在 mid 右边，但 mid 自己可能就是，所以 hi = mid；mid 是好的，答案一定在右边，lo = mid + 1。区间缩到一个点就是答案，只需约 log2(n) 次调用。
为什么正确
第一个坏版本始终在 [lo, hi] 中：lo 左边都已确认是好的，hi 已知是坏的（或为 n）。
复杂度分析
时间 O(log n)（接口调用次数），空间 O(1)。
易错点
写 mid = (lo + hi) // 2 在 C++/Java 里会因 lo + hi 超过 int 上限而溢出，要写 lo + (hi - lo) / 2。另外 mid 是坏的时要 hi = mid 而不是 mid - 1，否则会跳过答案。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def firstBadVersion(self, n: int) -> int:
lo, hi = 1, n
while lo < hi:
mid = lo + (hi - lo) // 2
if isBadVersion(mid):
hi = mid
else:
lo = mid + 1
return loclass Solution extends VersionControl {
public int firstBadVersion(int n) {
int lo = 1, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (isBadVersion(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}class Solution {
public:
int firstBadVersion(int n) {
int lo = 1, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (isBadVersion(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
};func firstBadVersion(n int) int {
lo, hi := 1, n
for lo < hi {
mid := lo + (hi-lo)/2
if isBadVersion(mid) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}var solution = function(isBadVersion) {
return function(n) {
let lo = 1, hi = n;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (isBadVersion(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
};var solution = function(isBadVersion: any) {
return function(n: number): number {
let lo = 1, hi = n;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (isBadVersion(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
};