LeetCode 278 First Bad Version（第一個壞版本）（二分法）（*）

LeetCode 278 First Bad Version（第一個壞版本）（二分法）（*）

翻譯

你是一個產品經理，目前正在帶領團隊去開發一個新產品。

不幸的是，產品的上一個版本沒有通過質量檢測。

因為每個版本都是建立在前一個版本基礎上開發的，所以壞版本之後的版本也都是壞的。

假設你有n個版本[1,2,...,n]，並且你想找出造成後面所有版本都變壞的第一個壞版本。

給你一個API——bool isBadVersion(version)，它能夠確定一個版本是否是壞的。

實現一個函數去找出第一個壞版本。

你應該盡可能少地去調用這個API。

原文

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.

分析

其實題目說了這麼多，解出來只需要用二分法就夠了，只不過中間挺容易出錯的。

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

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

今天寫的第六道題了，好累哎……