278.First Bad Version

Tags: [binary_search]

Com: {fb}

Link: https://leetcode.com/problems/first-bad-version/\#/description

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.

Solution: 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
        """

        # binary search
        start = 1
        end = n

        while start <= end:
            mid = start + (end - start) / 2
            if not isBadVersion(mid):
                # the first bad version must be on the right side.
                start = mid + 1
            else:
                # the first bad version counld be the mid or on the left side of mid.
                if (mid - 1 < start) or (mid - 1 >= start and not isBadVersion(mid - 1)):
                    return mid
                end = mid - 1

        return None

Revelation:

• The mid is bad version, means the mid could be the first bad version, or the first bad version on the left side of the mid. So we check whether mid - 1 < start, which means there is nothing on the left side of the mid, so mid is the first bad version. And we also check if mid - 1 >= start and not isBadVersion(mid - 1) means the element just on the left side of mid is not bad version, so mid is the first bad version.

Note:

• Time complexity = O(lgn), n is the the give input.