'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List
import bisect


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

class Solution:
    # T: O(logn), S: O(1)
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 1, n
        while l < r:
            mid = l + (r-l)//2
            if isBadVersion(mid):
                r = mid
            else:
                l = mid + 1
        return l
        
    
    # fancy
    def firstBadVersion1(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.__getitem__ = isBadVersion
        return bisect.bisect_left(self, True, 1, n)