278. First Bad Version （easy)

Q:

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 will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

A:

二分查找。 检测过得，标记出来，不去检查其邻居

// Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int low = 1, high = n; // cannot use high as n+1, as it can overflow int res = n; while(low <= high) // low is inclusive, high is exclusive { int mid = low + (high -low)/2; // cannot use (high+low)/2, may overflow if(isBadVersion(mid)) { res = mid; // possible high= mid-1; }else{ low = mid+1; } } return res; } };

Mistakes:

关键是一开始isBadVersion（）的结果的意思没有搞清楚

另外， high = n+1 会造成overflow,  mid  = (low+high)/2 也会overflow

********就是简单的二分查找 ***********不是最优的，有重复call API **************

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        return helper(0,n);
    }
    private int helper(int base, int n){// n indcates from 0   while base is the result 
        if(n <= 1)
            return base+n;
        int mid = (n+1)/2;
        if(isBadVersion(base+mid)){
            if( mid == 1 || !isBadVersion(base+mid-1))
                return base+mid;
            else
                return helper(base,mid-1);
        }else
            return helper(base+mid, n-mid);
    }
}

Note:
其实上面这个 k==0 和 k==1 可以合并在一起， 算了，清晰可读更重要