难度: Easy
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1：
输入：n = 5, bad = 4 输出：4 解释：调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true所以，4 是第一个错误的版本。
示例 2：
输入：n = 1, bad = 1 输出：1
提示：
1 <= bad <= n <= 231 - 1运行时间: 19 ms
内存: 16.0 MB
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
def firstBadVersion(self, n: int) -> int:
i = 1
j = n
while i <= j:
mid = (i + j) // 2
if isBadVersion(mid):
j = mid - 1
else:
i = mid + 1
return i
这个题解使用二分查找的思路来寻找第一个错误的版本。首先设定左右边界 i 和 j，分别指向版本范围的首尾。然后进入一个循环，每次取左右边界的中点 mid，调用 isBadVersion API 判断第 mid 个版本是否有错。如果有错，说明第一个错误的版本在 mid 的左边，缩小右边界 j 到 mid-1；如果没错，说明第一个错误的版本在 mid 的右边，缩小左边界 i 到 mid+1。当左右边界重合时，i 指向的就是第一个错误的版本，返回 i 即可。
时间复杂度: O(log n)
空间复杂度: O(1)
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
def firstBadVersion(self, n: int) -> int:
i = 1
j = n
while i <= j:
mid = (i + j) // 2
if isBadVersion(mid): # 如果 mid 是错误版本
j = mid - 1 # 将右边界左移
else:
i = mid + 1 # 否则将左边界右移
return i # 循环结束时，i 指向第一个错误的版本
在二分查找中，目标是缩小搜索范围直到找到第一个错误的版本。当确定`mid`版本是错误的时候，设置右边界`j`为`mid-1`是为了排除`mid`版本及其右侧的版本，因为我们已经知道`mid`是错误的，所以需要检查`mid`之前的版本是否为第一个错误的版本。如果设置`j`为`mid`，则会重复检查`mid`版本，从而降低效率且可能陷入无限循环。
当`i`和`j`相邻时，意味着`i = mid`，`j = mid + 1`。此时中点`mid`还是等于`i`。如果`mid`版本是错误的，则将`j`设置为`mid-1`，即`j`成为`i-1`，循环结束。如果`mid`版本不是错误的，则将`i`设置为`mid+1`，即`i`成为`j`，循环再次结束。因此，`i`和`j`相邻是确定第一个错误版本的关键步骤，这样可以确保不遗漏任何可能的版本，并最终`i`将指向第一个错误的版本。
在Python中，整数是动态大小的，这意味着它们可以扩展以容纳任何大小的整数，因此在使用标准整数时不会发生整数溢出。然而，在其他语言如Java或C++中，整数类型有固定的大小，可以通过使用`i + (j - i) / 2`来代替`(i + j) // 2`来避免整数溢出，这样可以防止在计算中点时两个较大的数字相加导致溢出。
这种二分查找方法确实可以确保找到的是第一个错误的版本。这是通过始终将搜索范围缩小到包含第一个错误版本的部分来实现的。每次迭代，如果`mid`是错误的，就移动右边界到`mid-1`；如果`mid`不是错误的，就移动左边界到`mid+1`。这样保证了当左右边界相遇时，`i`指向的必须是第一个错误的版本。可以通过设计测试用例，其中版本从某一点开始变为错误，并验证算法返回的是否为这个转变点，来验证这一点。