**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
This isn't O(lgn) but O((logn)2). For example think of n=1014 and 1014 being the first bad version. You'll first add 1+2+4+8+16+32+64+128+256, then you'll add 1+2+4+8+16+32+64+128, then you'll add 1+2+4+8+16+32+64, and so on.
Btw, what's up with the account upvoting your topics being called "symgates2"?
@StefanPochmann You are right, thanks for the example. It is lg(n) + lg(n/2) + lg(n/4) ... 1. Which is O(lgn)^2) in total.