你好！我是金牌教练。为了帮你高效、专业地创建 OJ（在线判题系统）测试数据，我为你编写了这个集成化的数据生成器与标程（Generator & Solver）。

虽然 LeetCode 原题的 $N=10^4$ 规模对于 $O(N)$ 暴力算法来说非常轻松，但在 NOI 竞赛中，我们通常会通过构造特定的边界数据来检验选手的代码健壮性。

一、 测试点设计矩阵

二、 数据生成器 C++ 代码

该程序采用 C++14 标准，逻辑清晰，不含递归，并使用了 mt19937 随机引擎确保数据分布的科学性。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>
#include <set>
#include <ctime>

using namespace std;

// --- 标程 (最优复杂度 O(log N)) ---
int solve(int n, int target, const vector<int>& nums) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// --- 数据生成逻辑 ---
void make_data() {
    mt19937 rng(time(0));
    uniform_int_distribution<int> dist(-9999, 9999);

    for (int t = 1; t <= 10; t++) {
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";
        ofstream fout(in_name);
        ofstream fans(out_name);

        int n, target;
        vector<int> nums;
        set<int> unique_nums;

        // 根据测试点矩阵设计规模
        if (t <= 2) n = 10;
        else if (t >= 8 && t <= 9) n = 1;
        else n = 10000;

        // 构造不重复有序序列
        if (t == 5) { // 保证 target 极小
            target = -9999;
            while (unique_nums.size() < (size_t)n) unique_nums.insert(dist(rng) + 100);
        } else if (t == 6) { // 保证 target 极大
            target = 9999;
            while (unique_nums.size() < (size_t)n) unique_nums.insert(dist(rng) - 100);
        } else if (t == 7) { // 保证 target 在缝隙
            target = 500;
            while (unique_nums.size() < (size_t)n) {
                int val = dist(rng);
                if (val != 500) unique_nums.insert(val);
            }
        } else {
            while (unique_nums.size() < (size_t)n) unique_nums.insert(dist(rng));
        }

        for (int x : unique_nums) nums.push_back(x);
        sort(nums.begin(), nums.end());

        // 设定特定位置的 target
        if (t == 3) target = nums[0];
        else if (t == 4) target = nums[n - 1];
        else if (t == 8) target = nums[0];
        else if (t == 9) target = nums[0] + 1;
        else if (t <= 2 || t == 10) {
            if (rng() % 2 == 0) target = nums[rng() % n]; // 50% 概率命中
            else target = dist(rng);
        }

        // 1. 输出 .in 文件
        fout << n << " " << target << "\n";
        for (int i = 0; i < n; i++) {
            fout << nums[i] << (i == n - 1 ? "" : " ");
        }
        fout << endl;

        // 2. 调用标程生成 .out 文件
        int result = solve(n, target, nums);
        fans << result << endl;

        cout << "Generated Case " << t << " successfully." << endl;

        fout.close();
        fans.close();
    }
}

int main() {
    make_data();
    return 0;
}

三、 生成器关键细节分析

1. 文件大小控制：

   • 本题数据量 $N=10^4$，数组中每个数字加上空格平均按 6 字节计算，.in 文件大小约为 60KB。
   • 10 个测试点总共约 0.6MB，远小于 2MB 的要求，非常方便在 OJ 系统上传。

2. 满足“不重复”约束：

   • 使用了 std::set 自动去重并排序，确保生成的 nums 严格满足题目“不重复”且“升序”的描述。

3. 计算稳定性：

   • 防溢出：标程中使用 mid = left + (right - left) / 2，这是在 NOI 比赛中防止 left + right 超过 int 上界的标准做法。
   • 非递归逻辑：数据生成器和标程均采用迭代写法，彻底杜绝了在大规模数据下的爆栈风险。

4. 区分算法复杂度：

   • 虽然对于 $10^4$ 规模暴力解法通常能通过，但对于第 5、6、7 个测试点，如果选手在代码中没有正确处理 target 超出数组边界或处于元素间隙的情况，线性扫描或者写得不精细的二分都会出错。
   • 优化提示：如果你需要完全卡死 $O(N)$ 暴力，只需将生成器中的 $N$ 改为 $10^6$。

四、 如何使用

1. 将上述代码复制到 C++ 编辑器。
2. 编译并运行。
3. 程序会在当前目录下自动生成 1.in, 1.out 到 10.out。
4. 将这些文件打包成一个 .zip 文件，即可上传到你的 OJ 题目后台。

你好！我是金牌教练。在算法竞赛（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 在数组最左边、最右边、以及不存在时的情况，彻底弄懂指针为何如此移动。加油！