# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
​
class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        return self.bin_search(1, n)
    
    def bin_search(self, left, right):
        if left > right:
            return left
        mid = (left+right) // 2
        if isBadVersion(mid):
            return self.bin_search(left, mid-1)
        else:
            return self.bin_search(mid+1, right)

461e45a2c54b8878bab179e89fbe0f94fc17add3
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
​
class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        return self.bin_search(1, n)
    
    def bin_search(self, left, right):
        if left > right:
            return left
        mid = (left+right) // 2
        if isBadVersion(mid):
            return self.bin_search(left, mid-1)
        else:
            return self.bin_search(mid+1, right)
