278. 第一个错误的版本

算法 LeetCode 简单难度二分查找

算法

发布日期: 2021-12-30

更新日期: 2021-12-30

文章字数: 593

阅读次数:

278.第一个错误的版本

一、题目

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

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

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

示例一：

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

示例二：

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

提示：

1 <= bad <= n <= 231 - 1

二、相关链接

题目链接：https://leetcode-cn.com/problems/first-bad-version/
参考题解：https://leetcode-cn.com/problems/first-bad-version/solution/di-yi-ge-cuo-wu-de-ban-ben-by-leetcode-s-pf8h/

三、解题思路

解法：二分查找
思路：true的左边全是true，false的右边全是false，所以可以理解为有序数组
步骤：
- 1.正常定义二分查找需要的变量：left、right、middle
- 2.判断middle的正确性
  - 2.1 正确 -> left移动到middle+1
  - 2.2 错误 -> right移动到middle（不减1是因为最终返回的是第一个right而不是第一个left）
- 3.while循环到最后left会与right重合，这就是最终结果

四、代码

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
  public int firstBadVersion(int n) {
    int left = 1;
    int right = n;

    while(left<right) {
      int middle = left + (right - left) / 2;

      //二分查找，中间点如果是true的，那么左边都为true
      //如果中间点是false的，那么右边都为false
      if(isBadVersion(middle)){
        //如果是false，那么result在左边（包含middle），因为结果是要输出第一个false的version
        right=middle;
      }else{
        //如果是true，那么result在右边（不包含middle）
        left=middle+1;
      }
    }

    return right;
  }
}