C++实现有序递增数组二分查找并输出位置或-1

好的，这是一个非常经典的**二分查找**问题。针对有序递增且无重复元素的数组，二分查找可以在 **O(log n)** 时间内找到目标值的位置。 下面我将为你提供一个**高效、清晰、易于理解**的 C++ 实现，并给出详细注释和注意事项。 --- ## 🎯 解题思路 二分查找的核心思想： 1. **确定查找范围**：用两个指针 `left` 和 `right` 分别指向数组的起始和末尾。 2. **计算中间位置**：`mid = left + (right - left) / 2` （防止 `(left+right)` 可能溢出）。 3. **比较中间值与目标值 x**： - 如果 `a[mid] == x`：找到目标，返回 `mid`（注意：题目要求位置从1开始，所以返回 `mid+1`）。 - 如果 `a[mid] < x`：说明 x 在右半部分，更新 `left = mid + 1`。 - 如果 `a[mid] > x`：说明 x 在左半部分，更新 `right = mid - 1`。 4. **重复步骤2-3**，直到 `left > right`，此时说明 x 不存在，返回 -1。 > 注意：题目要求输出的是**位置**（从1开始计数），而非索引（从0开始）。 --- ## 🧩 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int binarySearch(const vector<int>& arr, int left, int right, int x) { // 当 left > right 时，查找结束，未找到 while (left <= right) { // 防止溢出的中间位置计算 int mid = left + (right - left) / 2; if (arr[mid] == x) { // 找到目标，返回位置（索引+1） return mid + 1; } else if (arr[mid] < x) { // 在右半部分继续查找 left = mid + 1; } else { // 在左半部分继续查找 right = mid - 1; } } // 未找到，返回 -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, 0, n - 1, x); cout << result << endl; return 0; } ``` --- ## 📝 关键点解释 | 部分 | 说明 | |------|------| | `vector<int> arr(n)` | 动态数组，存储输入的 n 个整数 | | `left = 0`, `right = n-1` | 初始查找范围为整个数组 | | `mid = left + (right - left) / 2` | 防止 `(left+right)` 整数溢出的安全写法 | | `mid + 1` | 题目要求位置从1开始，所以索引要+1 | | `while (left <= right)` | 当范围有效时持续查找 | | 返回 -1 | 当 `left > right` 时说明目标不存在 | --- ## ⚠️ 常见陷阱 & 开发建议 1. **溢出问题** 在计算 `mid` 时，如果使用 `(left + right) / 2`，当 left 和 right 很大时可能溢出（虽然本题 `n <= 10^6` 不太可能溢出，但建议养成好习惯）。 ✅ 推荐写法：`mid = left + (right - left) / 2` 2. **边界处理** - `left` 和 `right` 的更新要准确：`left = mid + 1` 或 `right = mid - 1`，避免死循环。 - 当 `left == right` 时，循环仍然继续，直到判断出是否找到。 3. **位置与索引混淆** 题目要求输出位置（从1开始），而数组索引从0开始，容易忘记 +1。务必核对输出样例。 4. **输入规模** `n <= 10^6`，`vector<int>` 完全够用，但如果使用普通数组，建议开全局区或动态分配，避免栈溢出。 --- ## 📚 进阶扩展 - **递归写法**：二分查找也可用递归实现，但迭代法通常效率更高（无函数调用开销）。 - **查找第一个/最后一个等于 x 的位置**：当数组存在重复元素时，需对 `mid` 的边界做额外处理。 - **STL 替代**：C++ 标准库提供 `binary_search`、`lower_bound`、`upper_bound`，可用于快速实现功能。 ```cpp // 判断是否存在 bool exist = binary_search(arr.begin(), arr.end(), x); // 查找第一个 >= x 的位置 int pos = lower_bound(arr.begin(), arr.end(), x) - arr.begin(); ``` --- ## 💡 - 二分查找是针对有序数组的高效算法，时间复杂度 **O(log n)**。 - 注意**索引溢出**、**位置与索引转换**、**边界更新** 三个易错点。 - 本题的输入规模较大，建议使用 `scanf/printf` 进一步提高 IO 速度（但本题 C++ 的 `cin/cout` 加上 `ios::sync_with_stdio(false)` 也足够）。 --- ######[AI写代码神器 | 1245点数解答 | 2026-06-05 21:20:40]