有序递增数组二分查找 | C++ 枚举法与二分法对比实现

好的，这个问题是二分查找的经典应用场景。针对你给出的 C++ 列举法（暴力法）需求，以及二分查找的标准实现，我将提供两份代码：一份是**暴力枚举法**（用于对比），另一份是**高效二分查找法**。并给出详细的解析与注意事项。 --- ## 🧭 问题 你要求一个**有序递增数组**，使用**二分查找**找值 x 的位置（从0或1开始计数需按题目要求），若不存在输出 -1。输入规模： - 数组长度 n ≤ 10⁶ - 元素值范围 [1, 10⁸] - 查找值 x ∈ [0, 10⁸] **注意**：题目中的“列举法”在二分查找语境下通常指线性枚举，但为了匹配你的要求 —— 既给出二分查找，也对比展示“列举法”的写法。 --- ## ✅ 方案一：二分查找法（推荐） 二分查找的时间复杂度为 **O(log n)**，对于 n=10⁶ 足够快。 ### 📝 核心思路 1. 使用两个指针 `low` 和 `high` 指向数组的起始和末尾。 2. 计算中间位置 `mid = low + (high - low) / 2`（防止溢出）。 3. 若 `arr[mid] == x`，返回 mid（题目要求位置，可根据需要 +1 改为 1-based）。 4. 若 `arr[mid] < x`，则在右侧查找；否则在左侧查找。 5. 若循环结束未找到，返回 -1。 ### 💻 C++ 代码实现（二分查找） ```cpp #include <bits/stdc++.h> using namespace std; int binarySearch(const vector<int>& arr, int x) { int low = 0, high = arr.size() - 1; while (low <= high) { int mid = low + (high - low) / 2; // 防止溢出 if (arr[mid] == x) { return mid; // 若题目要求从1开始计数，则返回 mid+1 } else if (arr[mid] < x) { low = mid + 1; } else { high = mid - 1; } } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; ++i) { cin >> arr[i]; } int x; cin >> x; int pos = binarySearch(arr, x); cout << pos << endl; // 这里以0-based示例，若需要1-based可改为 pos+1 return 0; } ``` > ⚠️ **位置说明**： > 若题目输出要求是 **第几个元素**（从 1 开始计数），则将 `return mid` 改为 `return mid + 1`，且 -1 不变。 --- ## 🔍 方案二：枚举法（列举法） 枚举法时间复杂度为 **O(n)**，在 n=10⁶ 时仍可能在限定时间内通过（约 0.1~1 秒），但数据规模更大时可能超时。适合作为对比理解。 ### 💻 C++ 代码实现（枚举法） ```cpp #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; ++i) { cin >> arr[i]; } int x; cin >> x; int pos = -1; for (int i = 0; i < n; ++i) { if (arr[i] == x) { pos = i; // 如需1-based，改为 pos = i + 1 break; } } cout << pos << endl; return 0; } ``` --- ## 📊 两种方法对比 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | |------------|------------|------------|------------------------| | 二分查找 | O(log n) | O(1) | 有序数组，大规模数据 | | 枚举法 | O(n) | O(1) | 数据量小，或无序数组 | **建议**：在有序递增数组中，始终首选**二分查找**，效率高且代码简洁。 --- ## 🧠 关键概念解释 - **二分查找**：每次将搜索范围缩小一半，前提是数组**有序**。 - **mid 计算**：`low + (high - low) / 2` 可避免 `(low + high) / 2` 导致的整数溢出（当 low, high 接近 INT_MAX 时）。 - **循环条件**：`while (low <= high)` 表示区间为 `[low, high]`。若改为 `while (low < high)` 则需相应调整终止逻辑。 --- ## 🛠️ 常见陷阱与最佳实践 1. **数组索引从 0 还是 1 开始**：答题前确认题目要求，输出 `mid` 或 `mid+1`。 2. **重复元素**：题目明确“不存在相同元素”，可忽略此情况；若有重复，二分查找需改为查找**第一个**或**最后一个**位置。 3. **输入加速**：使用 `ios::sync_with_stdio(false); cin.tie(nullptr);` 可大幅提升 `cin` 速度。 4. **数值范围**：`x` 可能小于数组最小值或大于最大值，二分查找会正常返回 -1。 --- ## 📚 学习资源推荐 - [二分查找 - OI Wiki](https://oi-wiki.org/basic/binary/) - [C++ STL binary_search](https://en.cppreference.com/w/cpp/algorithm/binary_search) - 《算法竞赛入门经典》（刘汝佳）第二章 --- ## 💡 开发建议 1. **尽早处理边界条件**：如 n=0 或数组为空，直接返回 -1。 2. **使用 `lower_bound` / `upper_bound`**：C++ STL 提供了二分查找相关函数，如 `lower_bound(arr.begin(), arr.end(), x)` 返回第一个不小于 x 的迭代器。 3. **代码复用**：将二分查找封装成函数，便于测试和维护。 --- ######[AI写代码神器 | 1455点数解答 | 2026-06-05 21:08:41]