278. First Bad Version

題目網址：https://leetcode.cn/problems/first-bad-version/

題意：假設你有 n 個版本 [1, 2, ..., n], 請找出導致之後所有版本出錯的第一個錯誤的版本。

你可以通過調用 bool isBadVersion(version) API 來判斷 version 是否出錯。

盡量減少調用 API 的次數。

Solution：

想法：利用 Binary Search

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 0, right = n - 1;

        while (left <= right) {
            const int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
};

• time：$O(log(n))$ ➔ Binary Search
• space：$O(1)$ ➔ 只需常數空間