刷题第二篇：力扣278第一个错误的版本

「这是我参与11月更文挑战的第7天，活动详情查看：2021最后一次更文挑战」

前言

今天和大家分享一道简单的算法题，花哥算法不精，期待和小伙伴们多学习学习，在评论区指教一二，明天又要开始搬砖了，划起来。

题目分析

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

假设你有 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

根据题目要求，我们就是要用最少的查询次数，找到第一个错误版本，很显然，看完上一篇文章的小伙伴已经看出来了，这还是一个二分法的算法题，思想可以完全套用上一篇文章。

根据题目可以分析出：已知查找区间1到n，我们设置左边界、右边界，然后根据通过循环不断轮询，每次根据左右边界找出他们的中间值，如果中间值isBadVersion(mid)结果为false，那第一个错误版本区间可以判定为 [left,mid] ，然后修改右侧边界，通过这种方式，最终得到结果。

代码分析

• 代码示例

public int firstBadVersion(int n) {
    int left = 0,right = n,mid = 0;
    while (left < right){
        mid = left + ((right - left) >> 1);
        if (isBadVersion(mid)){
            right = mid;
        }else {
            left = mid+1;
        }
    }
    return left;
}
复制代码

• 类似的， mid = (left+ right) /2 。

• 然后调用isBadVersion方法，根据结果修改边界值：

  1. 若isBadVersion为true，表示错误版本在右侧区间 (mid,right] ，缩小左侧区间；
  2. 若isBadVersion为false，表示错误版本在左侧区间 [left,mid] ，缩小右侧区间；
  3. 轮询完成，返回最终结果left。

注意点

上面代码涉及到一个临界点问题，就是while这个等于到底带不带上，其实这个和边界取值有关：

• 不带等于号

while (left < right){
    mid = left + ((right - left) >> 1);
    if (isBadVersion(mid)){
        right = mid; //right=mid
    }else {
        left = mid+1;
    }
}
复制代码

• 带等于号

while (left < right){
    mid = left + ((right - left) >> 1);
    if (isBadVersion(mid)){
        right = mid-1; //right=mid-1
    }else {
        left = mid+1;
    }
}
复制代码

• 时间复杂度：O(log n)，其中 n 是给定版本的数量。
• 空间复杂度：O(1)。