题目

标题和出处

标题：第一个错误的版本

出处：278. 第一个错误的版本

难度

3 级

题目描述

要求

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错误的。

假设你有 $\text{n}$ 个版本 $\text{[1, 2, ..., n]}$，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用接口 $\text{bool isBadVersion(version)}$ 判断版本号 $\text{version}$ 是否在单元测试中出错。实现一个函数查找第一个错误的版本。你应该尽量减少调用接口的次数。

示例

示例 1：

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

示例 2：

输入：$\text{n = 1, bad = 1}$
输出：$\text{1}$

数据范围

• $\text{1}\le \text{bad}\le \text{n}\le {\text{2}}^{\text{31}}-\text{1}$

解法

思路和算法

用 $\text{bad}$ 表示第一个错误的版本。对于某个在范围 $[1,n]$ 中的版本，使用该版本调用接口得到结果。如果该版本是错误的，则 $\text{bad}$ 小于等于该版本；如果该版本是正确的，则 $\text{bad}$ 大于该版本。由于可以根据调用接口的结果缩小查找范围，因此可以使用二分查找得到 $\text{bad}$。

由于 $\text{bad}$ 一定在范围 $[1,n]$ 内，因此初始时二分查找的范围的下界和上界是 $\text{low}=1$，$\text{high}=n$。

每次查找时，取 $\text{mid}$ 为 $\text{low}$ 和 $\text{high}$ 的平均数向下取整，对 $\text{mid}$ 调用接口，根据结果调整二分查找的范围。

• 如果 $\text{mid}$ 是错误的，则 $\text{bad}$ 小于等于 $\text{mid}$，因此在范围 $[\text{low},\text{mid}]$ 中继续查找。

• 如果 $\text{mid}$ 是正确的，则 $\text{bad}$ 大于 $\text{mid}$，因此在范围 $[\text{mid}+1,\text{high}]$ 中继续查找。

当 $\text{low}=\text{high}$ 时，结束查找，此时 $\text{low}$ 即为 $\text{bad}$，返回 $\text{low}$。

代码

public class Solution extends VersionControl {public int firstBadVersion(int n) {int low = 1, high = n;while (low < high) {int mid = low + (high - low) / 2;if (isBadVersion(mid)) {high = mid;} else {low = mid + 1;}}return low;}
}

复杂度分析

• 时间复杂度：$O(\log n)$。二分查找的次数是 $O(\log n)$，每次查找的时间是 $O(1)$，时间复杂度是 $O(\log n)$。

• 空间复杂度：$O(1)$。