题目

分析

• 要查找，还要尽可能少比较次数，首先想到的就是二分查找。
• 要注意溢出问题

题解

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        long begin = 1;
        long end = n;
        while(begin<end){
            int mid = (int)((begin+end)>>1);
            if(isBadVersion(mid)&&end!=begin){
                end = mid;
            }else{
                begin = mid+1;
            }
        }
        return (long)begin;
    }
}

时间复杂度	空间复杂度
O(logn)	O(1)

• 官方的题解提供了一种更好的方法防止溢出

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

一点屁话

久违的一道简单题啊，考试暂告一段落，恢复打卡奥┗|｀O′|┛ 嗷~~