Leetcode刷题100天—278. 第一个错误的版本(排序)—day19

旧城等待， 2022-09-11 05:27 146阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210826233359680][]

#### [278. 第一个错误的版本][278.] ####

难度简单391收藏分享切换为英文接收动态反馈

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

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

package 排序;
    
    public class _278_第一个错误的版本 { 
        public int firstBadVersion(int n) { 
            int left=1,right=n,pivot;
            while(left<right&&left!=pivot) { 
            	pivot=left+(right-left)/2;
            	
            	if ( isBadVersion(pivot)) { 
            		right=pivot;// 答案在区间 [left, mid] 中
            		
    			}else { 
    				left=pivot+1;// 答案在区间 [mid+1, right] 中
    			}
            	
            }
            return left;
        }
        //n=6 bad=4
        /* * 123456 * 第一轮遍历 left=1 pivot=3 right=6 false * 第二轮遍历left=4 pivot=5 right=6 true * 第三轮遍历 left=4 pivot=4 right=5 true * 第四轮遍历 left=4 pivot=4 right=4 true 此时left<right结束循环，返回left */
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210826233359680]: /images/20220828/f74adceacf2047b98a66befd5b2beca5.png
[278.]: https://leetcode-cn.com/problems/first-bad-version/