**Edit: The time complexity is O(lgn)^2), not O(lgn)

Instead of binary search, we can use the trick we used when solving Pow(x, n)

```
class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
i = 0
while not (not isBadVersion(i) and isBadVersion(i+1)):
plus = 1
while i+plus <=n and not isBadVersion(i+plus):
i+=plus
plus*=2
return i + 1
```