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 havenversions[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 APIbool 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.

Credits: Special thanks [e-mail]for adding this problem and creating all test cases.

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