Easy

题目描述

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

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

给你一个 API 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 <= 2^31 - 1

解题思路

这是一道经典的二分查找题目。题目的关键在于找到第一个错误版本的位置。

思路分析：

由于错误版本之后的所有版本都是错误的，我们可以把这个问题想象成在一个有序数组中查找第一个满足条件的元素。版本序列可以看作：[好, 好, 好, ..., 坏, 坏, 坏, ...]，我们需要找到第一个"坏"的位置。

使用二分查找可以有效减少API调用次数：

  1. 设置左边界 left = 1，右边界 right = n
  2. 取中点 mid = left + (right - left) / 2，避免溢出
  3. 调用 isBadVersion(mid)：
    • 如果是错误版本，说明第一个错误版本在 [left, mid] 范围内，更新 right = mid
    • 如果是正确版本，说明第一个错误版本在 [mid+1, right] 范围内，更新 left = mid + 1
  4. 当 left == right 时，找到第一个错误版本

注意事项：

  • 使用 left + (right - left) / 2 避免整数溢出
  • 当找到错误版本时，不能排除当前版本，因为它可能就是第一个错误版本

代码实现

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

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

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

/* The isBadVersion API is defined in the parent class VersionControl.
      bool IsBadVersion(int version); */

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (IsBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

/**
 * 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 left = 1, right = n;
        while (left < right) {
            let mid = left + Math.floor((right - left) / 2);
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)二分查找的时间复杂度
空间复杂度O(1)只使用了常量级别的额外空间

相关题目