278 First Bad Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have
nversions[1, 2, ..., n]and you want to find out the first bad one, which causes all the following ones to be bad.You are given an API
bool isBadVersion(version)which will return whetherversionis bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.The Idea: Binary search until we are able to converge into the region that separates the last good version to the first bad version.
[1 1 1 1 1 1 1 1 1 1 0 0 0 0 0]
^
Complexity: O(logn) time and O(1) space through iterative binary search
# 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
"""
left, right = 1, n
while left < right:
mid = int(left + ((right - left) >> 1))
if not isBadVersion(mid): # search right
left = mid + 1
else: # search left
right = mid - 1
if isBadVersion(left):
return left
else:
return left + 1
Last modified 4yr ago