LeetCode第278题：第一个错误的版本-一一网

题干

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

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

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

示例:

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

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

所以，4 是第一个错误的版本。 
通过次数96,609提交次数223,000
复制代码

思路：二分

首先我们知道队列的构成时连续的false和连续的true，我们需要找到第一个true，所以我们在二分循环时判断一下结果为true的上一个是否为false即可。

代码实现：

执行用时：72 ms, 在所有 JavaScript 提交中击败了72.65%的用户

内存消耗：37.6 MB, 在所有 JavaScript 提交中击败了51.50%的用户

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function (isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function (n) {
        let max = n;
        let min = 1;
        let mid = 0;
        while (min <= max) {
            mid = Math.floor((max + min) / 2);
            let right = isBadVersion(mid - 1)
            let currentMid = isBadVersion(mid)
            if (currentMid) {
                if (!right) {
                    return mid
                }
                max = mid - 1
            } else {
                min = mid + 1
            }
        }
    };
};
复制代码