C++有序递增数组二分查找实现及边界处理详解

好的，这是一个非常经典的**有序数组二分查找**问题。下面我会为你提供完整的C++实现，并详细解释每一步的原理和注意事项。 --- ## 🔍 问题分析 我们有一个**递增**且**无重复元素**的数组，要在其中查找数值 `x`。 - 如果找到，返回其在数组中的**位置（下标）**，**注意**：题目没有明确说明下标是从0开始还是从1开始，一般来说算法题默认下标从0开始，但部分题目要求从1开始。我们这里先实现**0-based**，并在输出时根据需要调整。 --- ## 🧠 二分查找核心思路 1. 设定左边界 `L = 0`，右边界 `R = n - 1`。 2. 当 `L <= R` 时循环： - 计算中间位置 `mid = L + (R - L) / 2`（防止整数溢出）。 - 如果 `arr[mid] == x`，返回 `mid`。 - 如果 `arr[mid] < x`，说明目标在右侧：`L = mid + 1`。 - 如果 `arr[mid] > x`，说明目标在左侧：`R = mid - 1`。 3. 循环结束未返回，说明没找到，返回 `-1`。 --- ## 💻 C++代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int binarySearch(const vector<int>& arr, int x) { int L = 0; int R = arr.size() - 1; while (L <= R) { int mid = L + (R - L) / 2; // 防止 L + R 溢出 if (arr[mid] == x) { return mid; // 找到，返回下标 } else if (arr[mid] < x) { L = mid + 1; // 目标在右侧 } else { R = mid - 1; // 目标在左侧 } } return -1; // 没找到 } int main() { int n, x; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } cin >> x; int result = binarySearch(arr, x); // 如果题目要求位置从1开始，则输出 result + 1 // 如果位置从0开始，直接输出 result // 这里我们假设输出0-based下标（常见算法题默认） cout << result << endl; return 0; } ``` --- ## 📌 关键点解释 - **为什么用 `mid = L + (R - L) / 2` 而不是 `(L + R) / 2`？** 当 `L` 和 `R` 都接近最大整数时，`L + R` 可能溢出。使用减法可以避免这个问题。 - **为什么循环条件是 `L <= R`？** 当 `L == R` 时，区间内还有一个元素需要检查。如果条件写成 `L < R`，会漏掉最后一个元素。 - **为什么每次更新 `L` 或 `R` 要 `+1` / `-1`？** 因为 `mid` 已经检查过不是目标，可以安全地排除，避免死循环。 --- ## ⚠️ 常见陷阱与注意点 1. **数组下标从0开始 vs 从1开始** 如果题目输出要求位置从1开始（即第一个元素位置为1），则在 `return mid` 时改为 `return mid + 1`。 2. **数组元素范围** 题目中数组元素 `1 <= val <= 10^8`，`x` 范围 `0 <= x <= 10^8`，要注意 `x` 可能小于数组最小值或大于最大值，二分查找可以正确返回 `-1`。 3. **输入规模** `n <= 10^6`，二分查找时间复杂度 `O(log n)` 完全满足要求，无需担心性能。 4. **使用 `vector` 而非 `array`** 动态分配，方便处理可变大小，避免栈溢出。 --- ## 📂 进阶优化建议 - **递归实现**（不推荐用于大规模数据，可能栈溢出） 可以用递归写，但一般迭代更安全、高效。 - **泛型化** 可以将 `binarySearch` 写成模板函数，支持 `vector<int>`, `vector<long long>` 等。 - **STL 内置函数** C++ 标准库提供了 `std::binary_search`（返回 bool）和 `std::lower_bound`（返回迭代器），可用于快速实现，但面试或作业中往往要求手写。 --- ## 🧪 测试样例 **输入：** ``` 5 1 3 5 7 9 5 ``` **输出（0-based）：** ``` 2 ``` **输入：** ``` 4 2 4 6 8 10 ``` **输出：** ``` -1 ``` --- ## 🔗 学习资源推荐 - [C++ reference - binary_search](https://en.cppreference.com/w/cpp/algorithm/binary_search) - 《算法笔记》（胡凡）二分查找章节 - LeetCode 704. Binary Search --- **开发建议**： - 编写二分查找时，建议先明确输出是下标还是位置序号。 - 使用 `vector<int>` 而非原生数组，更安全。 - 多测试边界情况：x在开头、结尾、中间、不存在、小于最小值、大于最大值。 - 提交前请检查 `n=1` 时的正确性。 ######[AI写代码神器 | 1275点数解答 | 2026-06-05 21:14:21]