0278. 第一个错误的版本 #

标签：数组、二分查找
难度：简单

题目大意 #

描述：给你一个整数 n，代表已经发布的版本号。还有一个用于检测版本是否出错的接口 isBadVersion(version): 。

要求：找出第一次出错的版本号 bad。

说明：

要求尽可能减少对 isBadVersion(version): 接口的调用。
$1 \le bad \le n \le 2^{31} - 1$。

示例：

示例 1：

1
2
3
4
5
6
7


输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

1
2


输入：n = 1, bad = 1
输出：1

解题思路 #

思路 1：二分查找 #

题目要求尽可能减少对 isBadVersion(version): 接口的调用，所以不能对每个版本都调用接口，而是应该将接口调用的次数降到最低。

可以注意到：如果检测某个版本不是错误版本时，则该版本之前的所有版本都不是错误版本。而当某个版本是错误版本时，则该版本之后的所有版本都是错误版本。我们可以利用这样的性质，在 [1, n] 的区间内使用二分查找方法，从而在 $O(\log_2n)$ 次内找到第一个出错误的版本。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def firstBadVersion(self, n):
        left = 1
        right = n
        while left < right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

思路 1：复杂度分析 #

时间复杂度：$O(\log_2 n)$。二分查找算法的时间复杂度为 $O(\log_2 n)$。
空间复杂度：$O(1)$。只用到了常数空间存放若干变量。