Solving this question in linear time is pretty straightforward. This question is meant to be solved using binary search. Before diving into the solution, let’s see why we can solve this question using binary search. As mentioned in the question, the first bad version causes all the following version to be bad. So if version 5 is bad, all versions following 5, i.e., 6, 7, 8 and so on will be bad. Let us define our predicate as isBadVersion(i) which tells us whether a version i is bad. Let us say n=7 and the first bad version is 5. If we apply our predicate on each version, the resulting table would look something like this:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|:--:|:--:|:--:|:--:|:---:|:---:|:---:|
| no | no | no | no | yes | yes | yes |
Predicate: isBadVersion(i)
Clearly we can apply binary search in such cases. Here our binary search has to be left biased, i.e., we have to find the first occurrence of “yes”.
Recommended reading on binary search:
- TopCoder: Binary Search Fundamentals and Predicate Logic
- Binary Search Templates
- Binary Search Invariants
int firstBadVersion(int n) {
int l = 1, r=n;
while (l<r) {
int mid = l+(r-l)/2;
if (isBadVersion(mid))
r=mid;
else
l=mid+1;
}
return r;
}
Time complexity: O(logn)
Space complexity: O(1)