My binary search solution in Python with explanation

  • 0
    # 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
            0 1 2 3 4 5
            use binary search O(log n)
            if x is corrupt and x-1 not corrupt, then xth is the first version
            move pointer to left half if x is corrupt
            move pointer to right half if x is not corrupt
            def helper(left, right):
                x = (left + right) / 2
                # base case
                if x <= 0 or x == right:
                    return x
                # check x is a bad vers and if previous vers is not currupted
                # x is the first corrupted vers.
                if isBadVersion(x) and not(isBadVersion(x-1)):
                    return x
                if isBadVersion(x):
                    return helper(left, x-1)
                    return helper(x+1, right)
            return helper(1, n)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.