278. First Bad Version.md

278. First Bad Version (Esay)

Algorithm 1

• template binary search, need to consider if return left or right.

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 0, n - 1
        while(left <= right):
            mid = left + (right - left) // 2
            # if true, on the right side.
            if(isBadVersion(mid)):
                right = mid - 1
            else:
                left = mid + 1
        return left

Algorithm 2

• use a variable to record the last true element.

class Solution:
    def firstBadVersion(self, n):
        ans = -1
        left, right = 1, n
        while(left <= right):
            mid = left + (right - left) // 2
            print(mid)
            # if true, on the right side.
            if(isBadVersion(mid)):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans