79 - 第一个错误版本

题目

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

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

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

示例:

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

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

所以，4 是第一个错误的版本。

解答

感觉这个n就是一个有序数组啊，完全可以用二分法

var solution = function (isBadVersion) {
  var findBad = function (left, right) {
    while (left < right) {
      const mid = (left + right) >>> 1
      if (isBadVersion(mid)) {
        right = mid
      } else {
        left = mid + 1
      }
    }
    return right
  }
  return function (n) {
    return findBad(0, n)
  };
};

Runtime: 52 ms, faster than 66.30% of JavaScript online submissions for First Bad Version.

Memory Usage: 33.9 MB, less than 7.69% of JavaScript online submissions for First Bad Version.

惊呆了。。今天的leetcode没有go

image-20190911205259197

只好先写了再说

看了一眼题解，也没啥更好的方法了

这算是我第一次想到最优解？

测试代码

测试代码也不知道该怎么写，就只能写一个了。。

// ======= code ==========
// =======================
/**
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 */
var isBadVersion = function (version, ans = 4) {
  if (version >= ans) {
    return true
  }
  return false
};
/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function (isBadVersion) {
  /**
   * @param {integer} n Total versions
   * @return {integer} The first bad version
   */
  var findBad = function (left, right) {
    while (left < right) {
      const mid = (left + right) >>> 1
      if (isBadVersion(mid)) {
        right = mid
      } else {
        left = mid + 1
      }
    }
    return right
  }
  return function (n) {
    return findBad(0, n)
  };
};


// ======== 测试 ==========
const test = function () {
  const ans = solution(isBadVersion)(5)
  console.log("ans", ans)
}


// ========= data =============
const TEST_DATA = [
  {
    inputs: 5,
    target: 4
  },
];


// ==== 主函数 ======
var __main = () => {
  test()

  console.log("✅✅ all right")

}
__main()