First Bad Version

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.

分析

1. Given a integer 'n', we have to find out the first bad version, a integer 'i' before 'n' where isBadVersion returns true and false for i-1.
2. This is basically a binary search problem, each time you check if mid is the bad version between 0 and n, keep updating the start and end values. When you exit, check if mid is the bad version and return it, if not return mid+1.

图例

代码

//We just do a binary search between 0 and n, so it is O(log n) and space complexity is O(1).

public class FirstBadVersion extends VersionControl {
    public int firstBadVersion(int n) {
        //if(isBadVersion(n)) return n;
        int i=0, j =n, mid=0;
        while(i<=j){
            mid = i + (j-i) / 2;
            if(!isBadVersion(mid)) i = mid+1;
            else j = mid-1;
        }
        if(!isBadVersion(mid)) return mid+1;
        return mid;
    }
}