# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    
    def find_bad_version(self,n, start,end):
        if n==1 or n==0:
            return n
        mid = mid = (end - start)//2 + start
        mid_bad_version = isBadVersion(mid)
        pre_bad_version = isBadVersion(mid-1)
        
        if mid_bad_version is True and pre_bad_version is False:
            return mid
        elif mid_bad_version is False and pre_bad_version is False:
            start = mid+1
            return self.find_bad_version(n, start,end)
        elif mid_bad_version is True and pre_bad_version is True:
            end = mid-1
            return self.find_bad_version(n, start,end)
            
        
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        return self.find_bad_version(n,start=1,end=n)