class Solution:
    def get_first_bad_version(self, n):
        left, right = 1, n
        while left < right:
            mid = (left + right) // 2
            if not self.is_bad(mid):
                left = mid + 1 # this will avoid an infinite loop, because left <= mid < right
            else:
                right = mid
        
        return left

    def get_first_bad_version2(self, n):
        left, right = 1, n
        while left <= right:
            mid = (left + right) // 2
            if self.is_bad(mid):
                right = mid - 1
            else:
                left = mid + 1
        
        return left
    
    def is_bad(self, n):
        return n >= 4

solution = Solution()
print(solution.get_first_bad_version2(8))