leetcode筆記：First Bad Version

一. 題目描述

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.

二. 題目分析

題目說了一堆，一開始並不知道是想讓干什麼。後來去網上查了題意，引用如下：

你是一名產品經理，並領導團隊開發一個新產品。不幸的是，產品的最終版本沒有通過質量檢測。由於每一個版本都是基於上一個版本開發的，因此某一個損壞的版本之後的所有版本全都是壞的。

假設有n個版本[1, 2, …, n]，現在你需要找出第一個損壞的版本，它導致所有後面的版本都壞掉了。

提供給你一個API bool isBadVersion(version)，其功能是返回某一個版本是否損壞。實現一個函數找出第一個損壞的版本。你應該最小化調用API的次數。

原來只需實現類似於Search for a Range 的功能，判斷壞版本的函數bool isBadVersion(version)題目已經提供，無需糾結如何操作，這裡還是使用二分查找來解決問題。

三. 示例代碼

期初使用如下代碼一直提示：Time Limit Exceeded

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

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

檢查了一段時間，發現當n取很大的數時出現問題，原來是語句midIndex = (low + high) / 2; 直接相加時溢出，導致循環超時，該用以下代碼Accept。

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

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

四. 小結

該題的難度在Search for a Range 之下，但出現了數據溢出的問題，因此對於簡單一些的題也時刻不能掉以輕心啊。