278.第一个错误的版本.md

// 复习
// 二分法 二分查找

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        long mid = 0;
        // 二分法这里是left<=right，而双指针逼近是left<right。
        while (left <= right) {
            mid = ((long)left + (long)right) / 2;
        
            // 看起来下面的说法是错误的，因为对于这种简单的情况，二分法最后一定会找到答案。
            // 1 2
            // f t
            // l r
            // 此时mid=1为false，因此left=mid+1=2，然后left=right=2，mid=2为true，找到正确答案。
            if (isBadVersion(mid - 1) == false && isBadVersion(mid) == true) {
                // cout<<"A "<<mid<<endl;
                return mid;
            } else if (isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 这一步是走不到的，尝试任意返回。
        // cout<<"B "<<mid<<endl;
        return mid;
    }
};

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

核心思路：二分查找
比起常规的升序数组二分查找，此题更加容易，因为只有[f,f,f,f,t,t,t...] false和true两种，然后正常写二分查找的模板套路即可
[注] 经过推理，最后的mid计算出来，要么会在相邻f,t的f上，要么在相邻f,t的t上，所以要考虑两种情况，这两种情况都是可能发生的

class Solution {
public:
    int firstBadVersion(int n) {
        if (n == 0) return 0;
        long left = 1, mid = 0, right = n;
        while (left <= right) {
            mid = (left + right) / 2;
            if (isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;                
            }
        }
        return isBadVersion(mid) ? mid : mid + 1;
    }
};