【算法题解】67. 第一个错误的版本

小半 • 2023年12月28日上午11:48 • 数据结构 • 阅读 203

❝

这是一道 「简单」 题
https://leetcode.cn/problems/first-bad-version/

❞

题目

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

假设你有个版本，你想找出导致之后所有版本出错的第一个错误的版本。

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

示例 1:

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true

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

示例 2：

输入：n = 1, bad = 1
输出：1

提示：

题解

这是一道典型的 「二分查找」 的题目，满足其所有的条件：

目标函数（或者说待查找的序列）具有「单调性」。第一个错误版本及其之后的版本都是错的，前面的版本都是对的。
「具有边界」。最小的版本是，最大的版本是。
可以「通过索引进行访问」。通过检查即相当于通过索引访问。

解题思路比较简单，定义左右边界分别为，，然后取中间版本。

如果版本是错误版本，那么丢弃后面所有的版本，即，因为它们肯定不会是第一个错误版本。
如果版本是正确版本，那么丢弃以及其前面所有的版本，即，因为他们肯定都是正确版本，也就不会是第一个错误版本了。

直到当的时候，这个版本就是第一个错误版本。

代码实现

Java

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        int mid = 0;
        while(left < right){
            mid = left + (right - left) / 2;
            if(isBadVersion(mid)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }

        return left;
        
    }
}

Go

func firstBadVersion(n int) int {
    left, right := 1, n

    for left < right {
        mid := left + (right - left) / 2
        if isBadVersion(mid) {
            right = mid
        }else {
            left = mid + 1
        }
    }

    return left
}