Python 中的第一个错误版本

假设在一家公司里，一名产品经理带领着一个团队开发一款新产品。假设最新版本未通过质量检查。由于每个版本都是在前一个版本的基础上开发的，所以错误版本之后的所有版本都会错误。因此我们有一个元素为 [1, 2, … n] 的数组 A，我们必须从这个数组中找到第一个错误版本。

考虑我们有一个函数 isBadVersion(version_id)，它将返回版本是好还是坏。例如，假设 n = 5，版本 = 4 是第一个错误版本。因此如果 isBadVersion(3) 返回 false，isBadVersion(5) 返回 true，isBadVersion(4) 也返回 true，那么第一个错误版本就是 4

为了解决这个问题，我们将遵循以下步骤 -

  • 当 n < 2 时，返回 n
  • 使用给定的函数执行二分搜索方法来检测错误版本。

示例

让我们看看以下实现以更好地理解 -

 在线演示

first_bad = 0
def isBadVersion(version):
   if version >= first_bad:
      return True
   return False
class Solution:
   def firstBadVersion(self, n):
      if n <2:
         return n
      start = 1
      end = n
      while(start<=end):
         mid = (start+end)//2
         if isBadVersion(mid) and not isBadVersion(mid-1):
            return mid
         elif isBadVersion(mid-1):
            end = mid-1
         else:
            start = mid+1
ob1 = Solution()
first_bad = 4
op = ob1.firstBadVersion(5)
print(op)

输入

5
4

输出

4

更新日期： 2020 年 4 月 28 日

860 次观看

开启您的 职业生涯

完成课程以获得认证

开始
广告