// idea: instead of binary search on the [1,n] space,
// shrink the search space by locating the ending index of search range. This is achieved by continuously expanding length of search range by a factor of 2 until verion at the endind index becomes bad.
int firstBadVersion(int n) {
int start = 1, p = 0;
for(; start + (1LL << p) <= n && !isBadVersion(start + (1LL << p)); p++) {}
int end = min(1LL*n, start + (1LL << p));
start = start + (p>0?(1LL << (p1)) : 0);
while(start < end) {
int mid = start + (end  start) /2;
if(!isBadVersion(mid)) start = mid + 1;
else end = mid;
}
return start;
}
How about shrink the search space in the beginning. (real followup from interviews)


@ManuelP said in How about shrink the search space in the beginning. (real followup from interviews):
just looks like a bad idea, making the solution take about twice as long
This is for followup question. It may save a little time when n is very large and 1st bad version is very small.

@Kamikaze_coder Yes, but on average it makes it much slower. And how likely is it that the bug has existed since the early beginning? I'd say not likely. It's more likely that the bug was introduced recently or even in the middle.
I can imagine the idea being useful on the other end, though. Check n1, n2, n4, n8, n16, etc, until you find a good version. And then search after that. Because in reality, the bug was probably introduced recently^{[*]}. If this was indeed an interview question, I suspect this is what the interviewer meant.
[*] Also, it might be cheaper to test more recent versions than it is to test older versions because rolling the code back to recent versions requires fewer changes (unless you have all versions lying around explicitly)


@Kamikaze_coder After taking @ManuelP 's suggestions, updated the code as below:
int firstBadVersion(int n) { int end = n, p = 0; for(; end  (1LL << p) >= 0 && isBadVersion(end  (1LL << p)); p++) {} int start = max(0LL, end  (1LL << p)); end = end  (p>0?(1LL << (p1)) : 0); while(start < end) { int mid = start + (end  start) /2; if(!isBadVersion(mid)) start = mid + 1; else end = mid; } return start; }