class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
start = 1
end = n
if isBadVersion(start):
return start
while end - start > 1:
mid = (start + end) // 2
if isBadVersion(mid):
end = mid
else:
start = mid
return end