题目描述

你是一个产品经理，正在领导一个团队开发一款新的产品。很不幸，最新版本的产品在质检时失败了。由于每个版本的开发都是基于上一个版本的，所以从第一次质检失败的版本开始，之后所有的版本都会失败。

假设共有 n 个版本 [1, 2, ..., n]，现在请找出第一次失败的版本号。

给定一个API：bool isBadVersion(version) 可以返回 version 版本是否失败。请实现一个函数，找到第一个失败的版本号。你需要尽可能减少调用API的次数。

样例

给定 n = 5, version = 4 是第一个失败的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以4是第一个失败的版本。

算法

(二分) $O(logn)$

整个序列可以分为两段，前半段都是成功的版本，后半段都是失败的版本。所以该问题具有二分性质，直接二分即可。

时间复杂度分析：二分检索只会调用 $logn$ 次API，所以时间复杂度是 $O(logn)$。

C++ 代码

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

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