二分查找要求在已排序的序列中查找某个目标值，每次取中间元素进行比较，根据大小关系将搜索区间缩小一半，直到找到目标或区间为空。在C++中使用循环实现二分查找，既能避免递归的栈开销，也更容易控制边界条件。
C++循环实现二分查找
下面给出一个基于左闭右闭区间的循环写法，适用于升序数组。代码中使用mid = left + (right - left) / 2来防止left + right溢出。
#include <iostream>
#include <vector>
// 在升序数组arr中查找target，找到返回下标，否则返回-1
int binarySearch(const std::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; // 找到目标
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右半部分
} else {
right = mid - 1; // 目标在左半部分
}
}
return -1; // 未找到
}
int main() {
std::vector<int> data = {1, 3, 5, 7, 9, 11};
int idx = binarySearch(data, 7);
std::cout << "index: " << idx << std::endl;
return 0;
}
边界与常见错误
循环实现时最容易出错的是区间定义和更新方式不一致。如果采用左闭右开区间，则right初始化为arr.size()，且循环条件应为left < right，更新时right = mid。保持一种约定并贯穿始终即可减少bug。
循环与递归对比
- 循环版：无函数调用栈开销，空间复杂度O(1)
- 递归版：代码直观，但深度大时可能栈溢出
查找效率分析
二分查找每次将区间减半，最多比较次数为⌈log₂(n+1)⌉。其时间复杂度为O(log n)，远优于顺序查找的O(n)。空间复杂度在循环实现下为O(1)。
| 算法 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| 顺序查找 | O(1) | O(n) | O(1) |
| 二分查找（循环） | O(1) | O(log n) | O(1) |
适用场景
当数据量较大且已排序，或查找操作远多于插入删除时，使用C++循环实现的二分查找能明显提升效率。若数组频繁变动，维护有序性的成本可能抵消查找收益。
实际工程中可优先考虑标准库std::lower_bound等接口，但理解手写循环实现有助于排查边界问题。
c++binary_searchalgorithm_efficiency修改时间：2026-07-30 16:42:22