【LeetCode】 278. First Bad Version

Description

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.

你是一個PM且現在正在領導一個小組去開發一個新的產品。不幸地，你們產品的最新版本沒有通過品質確認。因為每個版本都是基於前一個版本開發，因此所有失敗版本後的版本也都是失敗的。

假設你有n個版本[1, 2, ..., n]且你想找出第一個失敗的版本，因為它造成後面每一個都失敗。

你有一個API bool isBadVersion(version) 可以回傳版本是否失敗。實作一個函式可以找到第一個失敗的版本。你應該最小化呼叫API的次數。

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

Solution

• 目標是找出API從false變成true的瞬間，除非第一個版本就是錯誤版本。
• 尋找的方法使用二分搜尋法，每次都檢查中間點是否為切換點：
  • 如果是切換點(isBadVersion(mid) != isBadVersion(mid + 1))，回傳中間點。
  • 如果在切換點後(都是true)，往前面找。
  • 如果在切換點前(都是false)，往後面找。

Code

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

class Solution {
public:
    int find(int s, int e)
    {
        double temp = (double)s + (double)e;
        int mid = temp / 2;
        if(isBadVersion(mid) != isBadVersion(mid + 1))
            return mid + 1;
        else if(isBadVersion(mid) == false)
            return find(s, mid);
        else
            return find(mid, e);
    }
    int firstBadVersion(int n) {
        if(isBadVersion(1)) return 1;
        return find(n, 1);
    }
};

tags: LeetCode C++