selected_coding_interview/docs/278. 第一个错误的版本.md
根据题目描述 “错误的版本之后的所有版本都是错的” ，说明给定的版本正确性列表是「有序的」，即以某个版本为分界点，左边（右边）都是正确（错误）版本。因此，考虑使用「二分查找」来查找首个错误版本。
本文使用与 704. 二分查找 相同的写法，二分查找缩窄区间的含义请参考代码注释。
若感觉动图播放太快，可以一页页看 $\downarrow$
<,,,,,,,,,>
class Solution:
def firstBadVersion(self, n: int) -> int:
i, j = 1, n
while i <= j:
# 向下取整除法计算中点 m
m = (i + j) // 2
# 若 m 是错误版本，则最后一个正确版本一定在闭区间 [i, m - 1]
if isBadVersion(m): j = m - 1
# 若 m 是正确版本，则首个错误版本一定在闭区间 [m + 1, j]
else: i = m + 1
# i 指向首个错误版本，j 指向最后一个正确版本
return i
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int i = 1, j = n;
while (i <= j) {
// 向下取整除法计算中点 m
int m = i + (j - i) / 2;
// 若 m 是错误版本，则最后一个正确版本一定在闭区间 [i, m - 1]
if (isBadVersion(m)) j = m - 1;
// 若 m 是正确版本，则首个错误版本一定在闭区间 [m + 1, j]
else i = m + 1;
}
// i 指向首个错误版本，j 指向最后一个正确版本
return i;
}
}
class Solution {
public:
int firstBadVersion(int n) {
int i = 1, j = n;
while (i <= j) {
// 向下取整除法计算中点 m
int m = i + (j - i) / 2;
// 若 m 是错误版本，则最后一个正确版本一定在闭区间 [i, m - 1]
if (isBadVersion(m)) j = m - 1;
// 若 m 是正确版本，则首个错误版本一定在闭区间 [m + 1, j]
else i = m + 1;
}
// i 指向首个错误版本，j 指向最后一个正确版本
return i;
}
};