你好！我是金牌教练。在处理这种“在大范围内寻找单一转折点”的问题时，从线性扫描到对数级检索的进化，不仅是效率的提升，更是竞赛思维的质变。

下面我为你演示这道题的代码演进过程。请注意，为了让代码能够独立运行，我在每个版本中都内置了一个简单的模拟交互接口。

版本 1：暴力扫描版 (Linear Scan)

思路提示： 最直观的方法是从版本 1 开始，一个一个往后问：“你是坏的吗？”。第一个回答“是”的版本就是答案。

复杂度分析：

• 时间复杂度：$O(n)$。如果 $n=2^{31}-1$，运算量约为 21 亿次。在 NOI 1s 时限下（通常处理 $10^8$ 次运算），这会产生严重的 TLE (Time Limit Exceeded)。
• 空间复杂度：$O(1)$。

/*
 * 暴力枚举法：从 1 到 n 逐一检查
 * 适用场景：n 规模较小（如 n <= 10^7）
 */
#include <iostream>

using namespace std;

// 模拟系统提供的接口
int first_bad; 
bool isBadVersion(int version) {
    return version >= first_bad;
}

int main() {
    int n;
    if (!(cin >> n >> first_bad)) return 0;

    // 从 1 开始线性扫描
    for (int i = 1; i <= n; i++) {
        if (isBadVersion(i)) {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

版本 2：递归二分版 (Recursive Binary Search)

思路提示： 利用坏版本出现后的“连带效应”（单调性），我们查看中间版本。如果是坏的，转折点在左边（含当前）；如果是好的，转折点在右边。

复杂度分析：

• 时间复杂度：$O(\log n)$。对于 21 亿的数据，最多只需询问 31 次。
• 空间复杂度：$O(\log n)$。由于使用了递归，系统栈会占用一定空间。

/*
 * 递归二分法：分治思想
 * 易错点：递归深度虽然只有 31 层，但在极严苛的空间限制下仍有风险。
 */
#include <iostream>

using namespace std;

int first_bad;
bool isBadVersion(int version) {
    return version >= first_bad;
}

int solve(int left, int right) {
    // 递归终止条件：搜索区间只剩一个点
    if (left == right) return left;

    // 关键点：防溢出写法。不能写 (left + right) / 2
    int mid = left + (right - left) / 2;

    if (isBadVersion(mid)) {
        // mid 是坏的，第一个坏版本在 [left, mid] 之间
        return solve(left, mid);
    } else {
        // mid 是好的，第一个坏版本在 [mid + 1, right] 之间
        return solve(mid + 1, right);
    }
}

int main() {
    int n;
    if (!(cin >> n >> first_bad)) return 0;
    cout << solve(1, n) << endl;
    return 0;
}

版本 3：最优解 - 迭代二分版 (Optimal Iterative)

思路提示： 这是 NOIP/NOI 竞赛中最稳健的写法。使用 while 循环避免了递归开销，且严格处理了整数溢出问题。

复杂度分析：

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(1)$。只用了三个变量，极其节省空间。

/*
 * 迭代二分法：NOI 满分规范
 * 关键点 1：使用 left < right 作为循环条件，退出时 left == right 必为答案。
 * 关键点 2：mid = left + (right - left) / 2 完美避开 int 溢出。
 */
#include <iostream>

using namespace std;

// 模拟系统提供的判定函数
long long first_bad_ver; // 使用 long long 模拟更大范围
bool isBadVersion(int version) {
    return (long long)version >= first_bad_ver;
}

int main() {
    long long n_input;
    if (!(cin >> n_input >> first_bad_ver)) return 0;
    
    // 注意：虽然 n 在 int 范围内，但为了安全，竞赛中常处理为 long long
    int left = 1;
    int right = (int)n_input;

    while (left < right) {
        // 易错点：这里如果写成 (left + right) / 2，
        // 当 left 和 right 都很大时（如 1.5e9），相加会超过 int 的 2.1e9，导致负数。
        int mid = left + (right - left) / 2;

        if (isBadVersion(mid)) {
            // 如果 mid 是坏的，说明答案在 [left, mid]
            // 注意这里不能是 mid - 1，因为 mid 自己可能就是第一个坏版本
            right = mid;
        } else {
            // 如果 mid 是好的，说明答案在 [mid + 1, right]
            left = mid + 1;
        }
    }

    // 循环结束时，left == right，指向第一个错误版本
    cout << left << endl;

    return 0;
}

时间复杂度优化建议与思考过程

1. 为什么不使用 std::lower_bound？ lower_bound 通常用于物理内存中的数组或容器。而本题是一个“隐式数组”，我们需要通过函数接口获取值。这种情况下，手写二分是唯一的选择。

2. 整数溢出的深度思考： 在 C++ 中，int 的最大值是 $2,147,483,647$。 题目给出的 $n = 2^{31}-1$ 刚好是这个最大值。

   • 如果执行 left + right：$21亿 + 21亿 = 42亿$，超出了 int 范围，发生溢出。
   • 如果执行 right - left：最大也就是 $21亿 - 1 = 21亿$，完全安全。
   • 结论：left + (right - left) / 2 是二分查找的“金科玉律”。

3. 读题时的关键词总结：

   • “错误版本之后的所有版本都是错的” $\rightarrow$ 确定了数据的单调分布（F, F, F, T, T, T），这是二分查找的物理基础。
   • “调用次数尽可能少” $\rightarrow$ 明确排除了 $O(n)$ 算法，指向 $O(\log n)$。
   • “第一个……” $\rightarrow$ 确定了二分的收缩方向，即找到满足条件的最小下标。

教练寄语：二分查找的代码虽短，但每一行都藏着细节。在考场上，一定要在草稿纸上模拟 left 和 right 相互靠近的过程，确保不会陷入死循环。加油！