LeetCode 75 Level 1 - Day 7 Binary Search

278. First Bad Version

• 題目連結
• 難易度：Easy

題目敘述

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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

預設函數

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

int firstBadVersion(int n) {

}

題目限制

解題過程及程式碼

本題是Binary Search的第二題，題目給一個數字 n表示[1, 2, ..., n]不同的版本，已知某個版本是壞的，也表示在這個版本之後的所有版本都是壞的，目標就是找出最先開始壞的版本，題目又提供了 isBadVersion這個函數讓我們可以輸入數字 n來查詢查詢版本的好壞；想法是由更新上下限來做逼近

• A. 確認中間點版本好壞?
• B. 若中間點壞了，則中間點右半部全壞了，下一個檢查的範圍就在中間點的左半部。
• C. 若中間點是好的，則中間點左半部全是好的，下一個檢查的範圍就在中間點的右半部。
• D. 重複以上過程直到左右邊界重合了就是我們的答案。

程式碼

int firstBadVersion(int n) {
    int next_n, next_n_start, next_n_size;

    int n_right_limit = n;
    int n_left_limit = 1;

    next_n_start = 1;
    next_n_size = n;

    /* 當n＝１時直接判斷版本的好壞 */
    if (n == 1) {
        if (isBadVersion(next_n_start)) {
            return 1;
        }
    }

    while (1) {
        next_n = next_n_start +  (next_n_size / 2);  // 找出區間的中間點

        /* 中間點是"壞"的 -> 中間點右邊全壞了，去檢查中間點的左半部找可能是最開頭的壞版本 */
        if (isBadVersion(next_n)) {
            n_right_limit = next_n;
            next_n_size = (next_n_size / 2);
        /* 中間點是"好"的 -> 中間點左邊全是好的，去檢查中間點的右半部找可能是最開頭的壞版本 */
        } else {
            next_n_start = next_n + 1;
            n_left_limit = next_n + 1;
            next_n_size = (next_n_size / 2);
        }

        if (n_right_limit == n_left_limit) {
            return n_right_limit;
        }
    }
    return -1;
}

第14天的發文就到這邊，謝謝大家!