C++有序递增数组二分查找算法实现及注意事项

我来帮您实现有序递增数组的二分查找算法。 ## 🔍 二分查找算法实现 ### 📋 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int binarySearch(const vector<int>& arr, int x) { int left = 0; int right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (arr[mid] == x) { return mid; // 找到目标，返回位置 } else if (arr[mid] < x) { left = mid + 1; // 目标在右半部分 } else { right = 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; // 执行二分查找并输出结果 cout << binarySearch(arr, x) << endl; return 0; } ``` ### 🎯 算法原理 二分查找的核心思想是**分而治之**，通过不断将搜索范围缩小一半来快速定位目标值。 **算法步骤：** 1. 初始化左右边界：`left = 0`, `right = n-1` 2. 循环直到 `left > right`： - 计算中间位置：`mid = left + (right - left) / 2` - 比较 `arr[mid]` 与目标值 `x`： - 相等：返回位置 `mid` - 小于：`left = mid + 1` - 大于：`right = mid - 1` 3. 未找到返回 -1 ### ⚠️ 注意事项 1. **边界处理**：使用 `left <= right` 而不是 `left < right` 2. **防止溢出**：`mid = left + (right - left) / 2` 比 `(left + right) / 2` 更安全 3. **索引从0开始**：题目要求的输出位置是从0开始计数的 4. **数组大小限制**：`n ≤ 10^6`，使用 `vector` 动态分配内存 ### 💡 开发建议 1. **输入优化**：对于大规模数据，考虑使用 `scanf/printf` 加快 IO 速度 2. **参数验证**：添加输入合法性检查 3. **代码复用**：将二分查找抽象为独立函数 4. **测试用例**： - 正常情况：查找存在的值 - 边界情况：查找第一个/最后一个元素 - 异常情况：查找不存在的值 - 特殊输入：n=1 的数组 ### 🚀 性能优化版 ```cpp #include <cstdio> #include <vector> using namespace std; int binarySearch(const vector<int>& arr, int x) { int left = 0, right = (int)arr.size() - 1; while (left <= right) { int mid = left + ((right - left) >> 1); // 位运算优化 if (arr[mid] == x) return mid; if (arr[mid] < x) left = mid + 1; else right = mid - 1; } return -1; } int main() { int n, x; scanf("%d", &n); vector<int> arr(n); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } scanf("%d", &x); printf("%d\n", binarySearch(arr, x)); return 0; } ``` ### 📊 算法复杂度 - **时间复杂度**：O(log n) - **空间复杂度**：O(1) ### ⭐ 常见问题 **Q1：二分查找的前提条件是什么？** A：数组必须是有序的，且元素不重复。 **Q2：为什么使用 `vector` 而不是数组？** A：`vector` 动态管理内存，避免栈溢出，适合大规模数据。 **Q3：如何处理查找不存在的元素？** A：循环结束时返回 -1 表示未找到。 ######[AI写代码神器 | 1028点数解答 | 2026-06-05 21:07:24]