你好！我是金牌教练。在算法竞赛（OI/NOIP）中，从“暴力线性扫描”进化到“对数级别检索”是每个选手的必修课。

下面我为你展示这道题的代码演进过程，带你从草稿纸上的逻辑一步步走向考场上的满分程序。

版本 1：暴力扫描版（Linear Search）

思路提示： 最简单的想法是：不管数组是否有序，我从头到尾看一遍，看到 target 就停下。

复杂度分析：

• 时间复杂度：$O(n)$。在 $n=10^4$ 的量级下，约进行 $10^4$ 次运算。
• 空间复杂度：$O(n)$（用于存储数组）。
• 优化建议：虽然对于此题能过，但如果 $n$ 增加到 $10^7$，线性扫描会超时（TLE）。我们没有利用“升序”这个核心条件。

/*
 * 适用场景：n <= 10^6, 且对时间要求不极端的题目
 * 易错点：数组下标从 0 开始，循环不要越界
 */
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, target;
    // 读入 n 和目标值
    if (!(cin >> n >> target)) return 0;
    
    vector<int> nums(n);
    int ans = -1;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        // 发现目标值，记录下标
        if (nums[i] == target) {
            ans = i;
            // 找到即停（假设数据不重复）
            break; 
        }
    }
    
    cout << ans << endl;
    return 0;
}

版本 2：递归二分版（Recursive Binary Search）

思路提示： 利用单调性，每次看中间的数。如果中间的数大了，就去左边找；小了就去右边找。这是一种“分治”思想。

复杂度分析：

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(\log n)$。因为递归会产生系统栈开销，每一层递归占用一定空间。
• 优化建议：在竞赛中，如果 $n$ 非常大且空间限制极严（如 2MB），递归可能会导致栈溢出（MLE/RE）。

/*
 * 易错点 1：(left + right) / 2 在 left, right 很大时会溢出 int 范围
 * 建议写法：left + (right - left) / 2
 * 易错点 2：递归基准情况（Base Case）必须写对，否则死递归
 */
#include <iostream>
#include <vector>

using namespace std;

int binarySearchRecursive(const vector<int>& nums, int left, int right, int target) {
    if (left > right) return -1; // 搜索区间为空，没找到

    int mid = left + (right - left) / 2;
    
    if (nums[mid] == target) return mid;
    
    if (nums[mid] > target) {
        // 中间值大了，在左半部分 [left, mid - 1] 找
        return binarySearchRecursive(nums, left, mid - 1, target);
    } else {
        // 中间值小了，在右半部分 [mid + 1, right] 找
        return binarySearchRecursive(nums, mid + 1, right, target);
    }
}

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    cout << binarySearchRecursive(nums, 0, n - 1, target) << endl;
    return 0;
}

版本 3：迭代二分版（Optimal Iterative - 考场标准版）

思路提示： 这是竞赛中最推荐的写法。使用 while 循环代替递归，将空间复杂度降到最低。

复杂度分析：

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(1)$（除了存储数组，只用了 3 个变量）。
• 思考过程：$10^4$ 的规模，$\log_2 10000 \approx 14$ 次比较。几乎是“瞬间”出结果。

/*
 * NOI 考场避坑指南：
 * 1. 循环条件：left <= right (保证最后一个元素也被检查)
 * 2. 边界更新：left = mid + 1, right = mid - 1 (防止死循环)
 * 3. 提速：大数据量建议使用 scanf/printf 或 cin.tie(0)
 */
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 竞赛提速技巧
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, target;
    if (!(cin >> n >> target)) return 0;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    int left = 0;
    int right = n - 1;
    int ans = -1;

    while (left <= right) {
        // 计算中点，采用防溢出写法
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            ans = mid;
            break; // 找到目标，跳出循环
        } else if (nums[mid] < target) {
            // 中间值比目标小，目标在右边，缩小左边界
            left = mid + 1;
        } else {
            // 中间值比目标大，目标在左边，缩小右边界
            right = mid - 1;
        }
    }

    cout << ans << endl;
    return 0;
}

时间复杂度优化建议总结

1. 防止整型溢出：在二分答案（Binary Search on Answer）题目中，left 和 right 可能是 $10^9$ 级别，left + right 会直接爆掉 int。养成使用 mid = left + (right - left) / 2; 的习惯。
2. STL 工具使用：在某些不需要手写二分的场景，C++ 提供了高度优化的函数：
   • std::binary_search：返回是否存在。
   • std::lower_bound：返回第一个 $\ge target$ 的迭代器。
   • std::upper_bound：返回第一个 $> target$ 的迭代器。 （但在 NOI 基础阶段，手写二分是必须掌握的基本功，因为题目经常要求你对二分过程进行变通处理。）
3. 循环终止条件：
   • 如果是 while (left <= right)，更新应为 left = mid + 1; right = mid - 1;。
   • 如果是 while (left < right)，更新应为 left = mid + 1; right = mid;。 根据草稿纸上的模拟选择最不容易出错的一种（推荐第一种）。

教练点评：二分查找虽然代码短，但边界处理是“魔鬼细节”。建议你在草稿纸上分别模拟 target 在数组最左边、最右边、以及不存在时的情况，彻底弄懂指针为何如此移动。加油！