前端刷题路-Day63：第一个错误的版本（题号278）-一一网

这是我参与更文挑战的第27天，活动详情查看：更文挑战

第一个错误的版本（题号278）

题目

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

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

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

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。 
复制代码

链接

leetcode-cn.com/problems/fi…

解释

这题啊，这题是经典二分。

主要是题目有个要求：

你应该尽量减少对调用 API 的次数。

二分的时间复杂度是O(logn)，而常规遍历的时间复杂度是O(n)，所以显然这题是我们用二分来解决。

当然了，正常的循环也能解决问题，而且代码量极少，就是性能较差。

知道了这题是二分，但这个二分和平常的二分有一点点小小的区别，边界问题。

常规二分的代码基本上是这样的?：

var mid = ~~((left + right) / 2)
if (isBadVersion(mid)) {
  right = mid - 1
} else {
  left = mid + 1
}
复制代码

重点是这两行?：

right = mid - 1
left = mid + 1
复制代码

在这题中，如果这样写则会有问题，有时候会漏掉正确答案，left的位置有可能在正确答案之前，也有可能就是正确答案。

为什么会这样呢？

让我们看看题目，题目的要求在正确版本号紧跟着就是错误的版本号，那么区间就是是这样的逻辑?：

如果mid是正确版本

那么第一个错误的版本号区间就在[mid + 1, right]中
如果mid是错误版本

按照经典二分的逻辑，第一个错误的版本号区间就在[left, mid - 1]中

错就错在这里了，由于错误的版本号必然在右侧，且mid是错误版本，那么如果区间值是[left, mid - 1]，那么mid - 1就有可能变为正确的版本号，如果继续二分，得到的left也就是只能是mid - 1，但第一个错误的版本号是mid，所以会导致最后的结果不对。

所以为了解决mid为错误的第一个版本号这种情况，这个区间就应该是[left, mid]。

所以此时的二分逻辑就应该是?：

var mid = ~~((left + right) / 2)
if (isBadVersion(mid)) {
  right = mid
} else {
  left = mid + 1
}
复制代码

自己的答案（暴力）

var solution1 = function(isBadVersion) {
  return function(n) {
    for (let i = 1; i <= n; i++) {
      if (isBadVersion(i)) return i
    }
  };
};
复制代码

经典暴力，没啥可说的，非常简单，但性能很差。

自己的答案（二分）

二分的逻辑在是解释部分已经说过了，这里直接看看代码?：

var solution = function(isBadVersion) {
  return function(n) {
    var left = 1
        right = n
    while (left < right) {
      var mid = ~~((left + right) / 2)
      if (isBadVersion(mid)) {
        right = mid
      } else {
        left = mid + 1
      }
    }
    return left
  };
};
复制代码