Python, understand (easily from Binary search idea)


  • 12
    W
    class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        r = n-1
        l = 0
        while(l<=r):
            mid = l + (r-l)/2
            if isBadVersion(mid)==False:
                l = mid+1
            else:
                r = mid-1
        return l

  • 13
    I

    Why r=n-1, l=0? I use n & 1 which look more natural.

    def firstBadVersion(self, n):
        i=1
        j=n
        while i<j:
            k=(i+j)/2
            if isBadVersion(k):
                j=k
            else:
                i=k+1
        return i

  • 0
    A

    my ugly binary search solution :)

    class Solution(object):
        def firstBadVersion(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n==0:
                return 0
            if isBadVersion(1):
                return 1
            return self.helper(1,n)
            
        def helper(self, start, stop):
            if isBadVersion(start):
                return start
            
            mid = (start+stop)//2
            if isBadVersion(mid):
                return self.helper(start,mid)
            else:
                return self.helper(mid+1,stop)
    

Log in to reply
 

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