Python实现"第一个错误的版本"的一种方法_第一个错误版本号利用python-CSDN博客

本文链接：https://blog.csdn.net/qiubingcsdn/article/details/82950352

你是一个产品经理，正在领导一个团队开发一个产品。不幸的是，你的产品没有通过最近的质量检测。因为每一个版本都是基于上一版本开发而来，所以某个错误的版本之后的所有版本都是错误的。

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

给定一个APIbool isBadVersion(version)用于判断某个版本是否错误。写一个函数查找第一个错误版本。该函数应该尽可能少的调用该API

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

1：二分法

def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        if isBadVersion(1):
            return 1
        first = 1
        last = n
        while first < last:
            mid = (first + last) // 2
            if not isBadVersion(mid) and isBadVersion(mid + 1):
                return mid + 1
            elif not isBadVersion(mid) and not isBadVersion(mid + 1):
                first = mid + 1
            elif isBadVersion(mid) and isBadVersion(mid + 1):
                last = mid

算法题来自：https://leetcode-cn.com/problems/first-bad-version/description/