[数组][二分]278. First Bad Version

题目：278. 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 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.

给一个数组表示商品质量，下标是［1，n］，从第i个开始是坏商品，找出第i个。
判断好坏的函数是 isBadVersion(i)，不过要尽可能的少使用这个函数。

第一判断是二分查找无疑。不过这题的几个特殊注意是：

1. mid = left + (right - left)/2; 不要用left＋right不然可能溢出。
2. 最后return的不是mid 而是left。
3. 递归条件不能是left <= right 不然可能无限递归。

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(n<1) return n;
        if(isBadVersion(1)) return 1;
        int left =1, right = n;
        int mid = 0;

        while(left < right){  //connot be the <=, or it will iterate infinitely
            mid =  left + (right - left)/2;
            if(!isBadVersion(mid)){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return left;//must be the left one!
        
    }
}

简洁版写法：

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {

        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right-left) / 2;
            if (!isBadVersion(mid)) left = mid + 1;
            else right = mid;            
        }        
        return left;
    }
}