class Solution {
public:
int firstBadVersion(int n) {
int lower = 1, upper = n, mid;
while(lower < upper) {
mid = lower + (upper  lower) / 2;
if(!isBadVersion(mid)) lower = mid + 1; /* Only one call to API */
else upper = mid;
}
return lower; /* Because there will alway be a bad version, return lower here */
}
};
Short C++ answer and minimize API calls


If you meet the first bad version during the loop, you cannot return it immediately, but you have to finish the loop and do some unnecessary checks, thus unnecessarily costs some extra time.
Here is my code, although it has two API calls in each loop, but it can return the answer immediately when finds it. I don't know which is better, cause the test sample is so small and I am no good at math..
// Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int low = 1, high = n, mid; while(low <= high){ mid = low + (high  low) / 2; if(!isBadVersion(mid)) low = mid + 1; else{ if(mid == 1  !isBadVersion(mid  1)) return mid; else high = mid  1; } } } };


@JulianWang12 The binary search complexity is O(logn). For example, n=1024, we only need to check 10 times. In your case, only when you find the target in 5 iterations(10 checks), you save something. The probability of stopping within 5 iterations is just 32 out of 1024, which is pretty small. In other words, you code will call more isBadVersion() in most cases.

@zilan (start + end) can overflow the int range and it will give a garbage value which will be divided by 2. start + (end  start)/2 does not let that happen. Keeps everything in the int range.