[100天算法】-第一个错误的版本（day 62）

题目描述

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
 
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
 
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
 
示例:
 
给定 n = 5，并且 version = 4 是第一个错误的版本。
 
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
 
所以，4 是第一个错误的版本。
 
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-bad-version
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1：二分法

思路

寻找最左边的满足条件的值

框架：

• 首先定义搜索区间为 [left, right]，左右都闭合。
• 循环搜索条件为 left <= right，只要区间内有元素就继续寻找。
• 循环体内，我们不断更新 mid ，并判断 mid 是否符合题目要求。
  • 如果 mid 符合要求，我们找到了一个备胎， 接着收缩右边界，继续看看左边还有没有。
  • 否则收缩左边界，去右侧寻找。
• 最后我们定点到 left 元素上，由于不会提前返回，因此我们需要检查最终的 left 是否符合要求。
  • 如果不符合题目要求，或者 left 出了右边的边界，说明没有找到，返回 -1。
  • 否则返回 left 即可。

复杂度

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

代码

Python Code

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r, m = 1, n, 0
        while l <= r:
            m = l + (r - l) // 2
            if isBadVersion(m): r = m - 1
            else: l = m + 1
        return l

        # 本题中“错误版本”一定存在，不然还是需要检查最终的左指针
        # return l if l <= n and isBadVersion(l) else -1