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

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

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

样例

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

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

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

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

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;//防止溢出，0ll在中间位置
            if (isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};