Python simple binary search solution


  • 0

    Take left most element and right most element, then calculate the mid point.
    If isBadVersion(mid) is True then you can discard right side of mid.
    Otherwise you can discard left side of mid, including mid itself.

    By including mid itself, we are at risk of infinite loop when left and right element is adjacient.
    Only in that case, we need to manually check left and right, then we can determine which is the first bad version.

    class Solution(object):
        def firstBadVersion(self, n):
            """
            :type n: int
            :rtype: int
            """
            l, r = 1, n
            
            while True:
                m = l + (r - l) / 2
                if isBadVersion(m):
                    r = m
                else:
                    l = m + 1
                
                if r - l == 1:
                    if isBadVersion(l):
                        return l
                    return r
                elif l >= r:
                    break
            return r
    

Log in to reply
 

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