278 First Bad Version

//你是个产品经理，发现product的最近版本fail了。目前已经开发到第n版（1,2，……，n）。找出在最早是哪个version开始坏的（其后的所有version都是坏的）
//给好API来判断是不是bad version: boolean isBadVersion(int n)
//二分 O(logn)
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(n < 1) return n;
        int start = 1, end = n;
        while(start + 1 < end){
            int mid = start + (end - start)/2 ;
            if(!isBadVersion(mid)){
                start = mid;
            }else{
                end = mid;
            }
        }
        if(isBadVersion(start)) return start;
        if(isBadVersion(end)) return end;
        return -1;
    }
}
//小follow： 如果boundary n不确定（n很大）：那就通过倍增法一步步试探找到边界
//前面加一句：
int bound = 1;
while(A[bound] < target){
     bound *= 2;
}
//找到bound，后面步骤一样