278. First Bad Version

Question

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Algorithm

Notice the question asks us to "minimize the number of calls to the API.", so we need implement a way as efficient as possible.

The version is sorted, and we need to find something, Ahh, binary search. But how? We use the following way to implement the binary search, find the boundary of the good and the bad.

When we meet good, we know the bad is behind it and when we meet bad, and the good is in front of it. By using this binary search, the final condition is left equals right and all the versions was check. The last checked version is a good version so the left was made of mid + 1 thus lying on the first bad. Or the last checked version a bad version and move forward becomes a good version. So it's the first bad.

Code

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}