LeetCode（初级算法）排序与搜索篇---第一个错误的版本

太过爱你忘了你带给我的痛 2022-05-25 11:57 84阅读 0赞

# 第一个错误的版本 #

## 题目 ##

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

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

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

## **示例** ##

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

## 解析 ##

因为True始终在False的右边，所以可以使用二分法来解决这个问题。但是要注意的是，这不同于数字的二分查找，因为在查找的过程中是无法确定最终的位置，所以需要注意low 与 high 赋值时的情况以及最后的返回值

1) 取中值
    f   f   f   f   f   t   t   t   t      (mid=l+(h-l)/2)
    l               mid             h
    
    2）h的取值
    f   f   t   t   t       （h = mid-1）
    l       mid     h
    *这里的h不可以赋予mid-1，因为我们并不清楚mid所处的位置是不是第一个
    
    3) l的取值
    f   t        （l = mid+1）
    l   h   
    mid
    *因为/2的结果是会向下取整的，如果将l=mid会造成l一直停留在一个位置不变

## 代码 ##

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */
    
    public class Solution { 
        public int firstBadVersion(int n) {
            int l = 1, h = n;         //l---低位 h---高位
            while (l < h) {
                int mid = l + (h - l) / 2;      //(1)
                if (isBadVersion(mid))
                    h = mid;                    //(2)
                else
                    l = mid + 1;                //(3)
            }
            return h;
        }
    }