LeetCode题解：第一个错误的版本

喜欢ヅ旅行 2022-12-28 01:55 120阅读 0赞

# 第一个错误的版本（easy） #

> 更好的阅读体验应该是：
> 
> 1.  审题-思考
> 2.  答题
> 3.  整理-归纳

## 一、题目 ##

[LeetCode：278.第一个错误的版本][LeetCode_278.]

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

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

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

**示例:**

给定 n = 5，并且 version = 4 是第一个错误的版本。
    
    调用 isBadVersion(3) -> false
    调用 isBadVersion(5) -> true
    调用 isBadVersion(4) -> true
    
    所以，4 是第一个错误的版本。

## 二、二分法解题 ##

二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

*  如果目标值等于中间元素，则找到目标值。
 *  如果目标值较小，继续在左侧搜索。
 *  如果目标值较大，则继续在右侧搜索。

时间复杂度：`O(logN)`。  
空间复杂度：`O(1)`。

## 三、基础模版II ##

1.  确定初始的左右边界:
    
     *  `left`: 0
     *  `right`: nums.length-1
     *  `mid`: (left + (right - left) >> 1)
2.  查找条件需要访问元素的直接右邻居。
3.  使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
4.  保证查找空间在每一步中至少有 2 个元素。
5.  需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

## 四、题解 ##

**分析模版**

*  我们的目标是：寻找出错的版本
    
     *  如果mid值出错，`证明出错的版本 <= mid`，那么右侧就可以抛弃了
     *  如果mid值没出错，`证明出错的版本 > mid`，那么左侧就可以抛弃了

看基础模版II，`版本判断函数`在帮助我们判断`mid值右侧`是否有错误的值。

**Javasciprt 代码**

/** * @param {function} isBadVersion() * @return {function} */
    var solution = function(isBadVersion) { 
        /** * @param {integer} n Total versions * @return {integer} The first bad version */
        return function(n) { 
            let min = 0;
            let max = n;
            // 因为mid = mid = max是结束的源头，所以不能相等
            while(min < max){ 
                let mid = min + ((max - min) >> 1);
                if(isBadVersion(mid)){ 
                    // 出错版本，可能是初始版本，所以保留
                    max = mid;
                }else{ 
                    min = mid + 1;
                }
            }
            return min;
        };
    };

如果大家对 min < max 存在疑问，可以看下面的代码

两种解法一样，我们不需要过于纠结～

## 五、写在最后 ##

本文是二分查找-模版II 的第一题，后面的几道题的也算是本模版的微调，加油～

如果对你有所帮助不妨给本项目的[github 点个 star][github _ star]，这是对我最大的鼓励!

**关于我**

*  花名：余光
 *  WX：j565017805
 *  沉迷 JS，水平有限，虚心学习中

**其他沉淀**

*  [JavaScript 版 LeetCode 题解][JavaScript _ LeetCode]
 *  [前端进阶笔记][Link 1]
 *  [CSDN][]

![yuguang-csdn-bottom.gif][]

[LeetCode_278.]: https://leetcode-cn.com/problems/first-bad-version/
[github _ star]: https://github.com/webbj97/summary
[JavaScript _ LeetCode]: https://webbj97.github.io/leetCode-Js/
[Link 1]: https://webbj97.github.io/summary/
[CSDN]: https://yuguang.blog.csdn.net/
[yuguang-csdn-bottom.gif]: /images/20221120/898fee602bdb4932ae7931a90addbe19.png