# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
def isBadVersion(version):
if version >= 71:
return True
else:
return False
# 16ms
class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
直接 range(n, 0, -1) 会报 MemoryError 错误
思路:二分查找
"""
# pre = 1
# for i in range(n, 0, -1):
# if isBadVersion(i):
# return pre
# pre = i
left = 0
right = n
while True:
mid = (left + right) // 2
if isBadVersion(mid) == False and isBadVersion(mid+1) == True:
return mid + 1
elif isBadVersion(mid) == False and isBadVersion(mid+1) == False:
left = mid
elif isBadVersion(mid) == True and isBadVersion(mid+1) == True:
right = mid
# leetcode 上最优解 4ms
class Solution2(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
if not isBadVersion(n): return n
left = 1
right = n
while left < right:
mid = (left + right) >> 1
if not isBadVersion(mid):
left = mid + 1
else:
right = mid
return left
n = 1004
s = Solution()
print(s.firstBadVersion(n))
网友评论