My binary search solution in Python with explanation


  • 0
    D
    # 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
            """
            """
            ex) 
            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)
                else:
                    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.