278 First Bad Version

278. First Bad Version

1. 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 havenversions[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 APIbool isBadVersion(version)which will return whetherversionis bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

2. Implementation

(1) Binary Search

思路：这题是关于git bisect的原理，本质是二分法找左边界问题，注意将数据转换成long类型，避免data overflow

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        long start = 1, end = n, mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;

            if (!isBadVersion((int)mid)) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return isBadVersion((int)start) ? (int)start : (int)end;
    }
}

3. Time & Space Complexity

Binary Search: 时间复杂度O(logn), 空间复杂度O(1)