qiaoxu123
3/13/2019 - 12:08 AM

278. First Bad Version

排序查找类问题。

最简单的方法是使用暴力查找，从0开始找，找到第一个值为true的数即可。但是这样效率太低。于是尝试用查找方法

二分查找是最常用的查找方式，在这需要注意的是判断初始值是否为true，此时第一个产品为假，则后续判断无效。

brute_froce.cpp
content_copyfile_download
//Runtime: 7024 ms, faster than 5.27%
//Memory Usage: 8.2 MB, less than 14.96%

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int i = 0;
        while(!isBadVersion(i)){
            i += 1;
        }
        return i;
    }
};
BinarySearch.cpp
content_copyfile_download
//Runtime: 4 ms, faster than 100.00%
//Memory Usage: 8.2 MB, less than 17.32%

class Solution {
public:
    int firstBadVersion(int n) {
        long begin = 1;
        long end = n;
        long temp;
        if(isBadVersion(1)) return 1;
        while(1){
            temp = (begin + end)/2;
            if(temp == begin)
                return end;
            if(isBadVersion(temp))
                end = temp;
            else
                begin = temp;
            // cout << "begin = " << begin << " " << "end = " << end << endl;
        }
    }
};