首页二分法查找c++

二分法查找c++

时间: 2025-04-21 16:38:10 浏览: 23

### C++ 中的二分查找算法实现在有序数组上执行二分查找是一种高效的搜索方法。该算法通过反复将待查区间减半来快速定位目标元素的位置。对于给定的一个升序排列的整数数组 `arr` 和一个要查找的目标值 `target`，可以按照如下方式编写二分查找函数： ```cpp #include <vector> using namespace std; int binarySearch(const vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (arr[mid] == target) { return mid; // 找到目标返回索引位置 } if (arr[mid] < target) { left = mid + 1; // 调整左边界 } else { right = mid - 1; // 调整右边界 } } return -1; // 如果未找到则返回-1表示不存在此元素 } ``` 上述代码展示了如何在一个已排序好的向量中寻找特定数值并返回其下标；如果找不到，则给出 `-1` 表明没有匹配项[^3]。 #### 复杂度分析时间复杂度 O(log n)，其中 n 是输入列表长度。这是因为每次迭代都会使搜索范围缩小一半。空间复杂度为 O(1)，因为只需要常数级别的额外存储空间用于保存指针变量和其他辅助数据结构。

阅读全文