C++二分查找实现：在有序数组中查找目标数字的位置

好的，我们来编写这个程序。这是一个典型的二分查找问题。 ## 🎯 问题分析 题目要求： - 输入：已排序的 `n` 个不同整数，以及一个目标值 `k` - 输出：`k` 在数组中的位置（从 1 开始计数），若不存在则输出 `n+1` **关键点**： - 数组已排序（从小到大） - 数字各不相同 - 数据规模 `n <= 100000`，二分查找效率为 O(log n)，完全可行 ## 💻 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int binarySearch(const vector<int>& arr, int n, int k) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (arr[mid] == k) { return mid + 1; // 返回位置（从1开始） } else if (arr[mid] < k) { left = mid + 1; } else { right = mid - 1; } } // 未找到，返回 n+1 return n + 1; } int main() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } int k; cin >> k; int result = binarySearch(arr, n, k); cout << result << endl; return 0; } ``` ## 🔍 代码解释 | 部分 | 说明 | |------|------| | `left = 0, right = n - 1` | 初始化查找区间为整个数组 | | `mid = left + (right - left) / 2` | 计算中间索引，防止 `(left+right)` 溢出 | | `arr[mid] == k` | 找到目标，返回 `mid + 1`（题目要求位置从1开始） | | `arr[mid] < k` | 目标在右半部分，收缩左边界 | | `arr[mid] > k` | 目标在左半部分，收缩右边界 | | 返回 `n + 1` | 未找到时的输出要求 | ## 🧪 验证示例 **示例 1**： ``` 输入： 5 1 2 3 4 5 3 过程： mid=2 -> arr[2]=3 == k -> 返回 2+1=3 输出：3 ``` **示例 2**： ``` 输入： 4 1 3 5 7 5 过程： mid=1 -> arr[1]=3 < 5 -> left=2 mid=2 -> arr[2]=5 == k -> 返回 2+1=3 输出：3 ``` **未找到的情况**： ``` 输入： 3 10 20 30 25 过程： 最终 left>right，退出循环 返回 n+1 = 4 输出：4 ``` ## ⚠️ 开发建议与注意事项 1. **防止整数溢出**：使用 `mid = left + (right - left) / 2` 而不是 `mid = (left + right) / 2`，当 `left` 和 `right` 都很大时后者可能溢出。 2. **注意索引转换**：数组索引从 0 开始，题目要求位置从 1 开始，返回时要加 1。 3. **边界条件处理**：`while (left <= right)` 这个条件很关键——当 `left == right` 时依然需要检查最后一个元素。 4. **题目特殊输出**：不存在时输出 `n+1` 而非常见的 `-1`，这点容易忽略。 5. **输入优化**：如果数据量更大（超过 10^5），建议使用 `ios::sync_with_stdio(false);` 和 `cin.tie(nullptr);` 加速输入。 ######[AI写代码神器 | 910点数解答 | 2026-05-29 19:25:28]