跳转到主内容
新派编程网 - 新潮编程理念，全新技术课堂！
📁 网站地图

C++如何实现二分查找的左边界查找_C++搜索算法细节问题解析【算法】

林译川
林译川
• 👁 0人浏览过
left_bound函数应设left=0、right=n，循环条件为leftleft
停在第一个满足
nums[i] >= target
的位置，不是“等于就返回”，而是“收缩右边界直到确定最左位置”。常见错误是把循环条件写成
left 却在更新时用 right = mid
，导致死循环或越界。 正确写法必须统一用
left 或全用 left ，且更新逻辑要匹配。推荐闭区间写法（更直观）：
int left_bound(vector& nums, int target) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; // 关键：相等也收缩右边界 } } return left; // left 是第一个 >= target 的下标 }
循环结束后
left
一定落在合法范围
[0, nums.size()]
内，无需额外判断越界 若
target
比所有元素都大，
left == nums.size()
，此时查不到，需调用方判断 不要用
(left + right) / 2
，防整数溢出，一律用
left + (right - left) / 2
为什么 else 分支里不能写 return 左边界要求“继续往左找”，所以遇到
nums[mid] == target
时绝不能返回，否则会错过更左的相同值。典型错误是把二分查找模板直接套过来，在
==
分支加
return mid
，这实际退化成了普通二分查找，不是左边界。 正确做法是把
==
和
>
合并在
else
中，统一执行
right = mid - 1
如果硬要拆开写，必须确保
==
时不退出，例如：
if (nums[mid] == target) right = mid - 1;
很多初学者在这里混淆“找到一个”和“找到最左一个”，本质区别就在是否允许继续收缩左/右边界 std::lower_bound 能不能直接替代手写 可以，但要注意接口差异和迭代器语义。标准库的
std::lower_bound
返回的是迭代器，不是下标，且要求容器已排序、支持随机访问。 C知道 CSDN推出的一款AI技术问答工具 下载 立即学习 “ C++免费学习笔记（深入） ”； 使用方式：
auto it = std::lower_bound(nums.begin(), nums.end(), target);
得到下标需手动计算：
int idx = it - nums.begin();
如果
it == nums.end()
，说明没找到左边界，等价于手写版中
left == nums.size()
性能上无差别，但手写更利于调试边界逻辑；用标准库则更安全，避免手误（比如漏掉
+1
或错用
mid
） 注意：它底层也是闭区间逻辑，行为和上面手写版完全一致 数组为空或全小于 target 时 left 的值怎么理解 这是最容易忽略的边界场景。空数组时
nums.size() == 0
，初始
right = -1
，循环不执行，直接返回
left = 0
—— 这个
0
正确表达了“第一个 >= target 的位置在索引 0 处（即插入位置）”。全小于 target 时，
left
最终等于
nums.size()
，表示应插入到末尾。 这两个值都不是“错误”，而是左边界定义的自然结果：它返回的是插入位置，不是“是否存在” 是否算“找到”，取决于业务逻辑：需要判断
left
很多人卡在这一步，是因为默认认为返回值必须是有效下标，其实左边界本质是“有序插入点”

相关文章