leetcode 278. 第一个错误的版本 python

题目描述

题解 还是典型二分

需要注意的是 题目中的bool isBadVersion(version)返回的true和false不代表当前版本version是否正确 恰好相反 返回true表示当前版本错误 返回false表示当前版本正确。

因此 第一个错误版本i应该满足

1 isBadVersion(i) true  

2 isBadVersion(i-1) false

isBadVersion(i) true且isBadVersion(i-1) true 说明i为错误版本但不是第一个错误版本。

isBadVersion(i) false说明当前版本正确 错误的版本在之后。

class Solution(object):
 def firstBadVersion(self, n):
 if n 1:
 return 1
 left 1
 right n
 while left right:
 mid left (right-left)//2
 if isBadVersion(mid) False:
 left mid 1
 else:
 if isBadVersion(mid-1) True:
 right mid-1
 else:
 return mid
 return left