递归版二分查找必须严格控制边界以避免栈溢出或死循环，关键在于每次递归缩小搜索范围且终止条件覆盖所有退出路径，常见错误是未正确处理left>right而直接返回-1。
递归版二分查找必须控制好边界，否则栈溢出或死循环
递归实现的关键在于每次调用都必须缩小搜索范围，且终止条件要覆盖所有退出路径。常见错误是写成 left 却在递归调用时传入 <code>mid 而非 mid - 1 或 mid + 1，导致区间不收缩。
正确做法是：当 target != arr[mid] 时，左半段递归调用传 left, mid - 1，右半段传 mid + 1, right；终止条件为 left > right，返回 -1。
int binarySearchRecursive(const vector<int>& arr, int left, int right, int target) {
if (left > right) return -1;
int mid = left + (right - left) / 2; // 防止整型溢出
if (arr[mid] == target) return mid;
if (target < arr[mid])
return binarySearchRecursive(arr, left, mid - 1, target);
else
return binarySearchRecursive(arr, mid + 1, right, target);
}
- 务必用
left + (right - left) / 2计算mid，避免left + right溢出 - 递归深度最大为
O(log n)，对超大数组（如千万级）仍安全，但调试时注意编译器默认栈大小限制 - 函数参数建议全用
const引用传递数组，避免拷贝开销
非递归版要注意 while 循环的更新顺序和退出条件一致性
非递归版本更常用，但新手常把 left 和 right 更新写反，或在 while 条件里用 却在分支里漏掉某一边的更新，造成无限循环。
核心原则：只要区间非空（即 left ），就继续查；每次比较后，要么排除 <code>mid 本身，要么排除它左边/右边全部元素。
立即学习“C++免费学习笔记（深入）”；
int binarySearchIterative(const vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (target < arr[mid])
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
-
while条件必须与递归终止条件一致，即left ，不是 <code> - 更新
right = mid - 1和left = mid + 1是刚性要求，不能写成right = mid—— 否则可能卡在单元素区间反复循环 - 该版本无函数调用开销，缓存友好，适合高频调用场景（如在线服务中的索引查询）
当数组含重复元素时，标准二分只返回“某个”位置，需额外处理找左右边界
原题中的递归/非递归版本都只解决「是否存在」和「任一位置」问题。如果需求是找第一个或最后一个出现位置（例如 lower_bound / upper_bound），不能简单复用上面逻辑。
关键差异在于：相等时不立即返回，而是继续向左（找首次）或向右（找末次）收缩区间。
例如找左边界：
int lowerBound(const vector<int>& arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target)
left = mid + 1;
else
right = mid; // 相等也收缩右边界，不停留
}
return left; // left == right，可能越界
}
- 这里用
left 作循环条件，<code>right初始化为arr.size()（开区间习惯），避免 -1 判断 - 相等时设
right = mid，不是mid - 1，才能保证不跳过首个匹配点 - 返回前应检查
left是否在有效范围内且arr[left] == target，否则说明不存在
C++ 标准库已有成熟实现，业务代码优先用 std::lower_bound 和 std::binary_search
手写二分容易出错，尤其在边界、符号、溢出、迭代器类型上。STL 版本经过充分测试，支持任意满足 RandomAccessIterator 的容器，且内联优化充分。
常用组合：
// 判断存在性 bool found = binary_search(arr.begin(), arr.end(), target); <p>// 查找首个不小于 target 的位置 auto it = lower_bound(arr.begin(), arr.end(), target);</p><p>// 查找首个大于 target 的位置 auto it2 = upper_bound(arr.begin(), arr.end(), target);</p><p>// 二者结合得重复区间 [it, it2) int count = distance(it, it2);
-
lower_bound和upper_bound返回的是迭代器，不是下标，需要减begin()才得索引 - 它们要求容器已排序，且比较操作符一致（比如都用
），否则行为未定义 - 自定义类型使用时，必须提供合法的
operator<或传入比较函数对象
实际工程中，除非在嵌入式等极端受限环境，或教学/算法题场景，否则不建议手写二分。标准库版本更稳、更短、更易读，且能随编译器升级自动受益于底层优化。边界细节和迭代器抽象已经帮你扛住了。
