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

c++中如何实现二分查找算法_c++高效查找算法实现【核心】

林译川
林译川
• 👁 0人浏览过
std::lower_bound比手写二分更安全，因其自动处理边界条件、整数溢出和迭代器失效；C++20起可用std::midpoint避免回绕；查找失败时推荐返回迭代器或std::optional，避免无符号类型下-1转极大值的bug。 std::lower_bound 为什么比手写二分更安全 因为边界条件、溢出、迭代器失效这些坑，
std::lower_bound
全部帮你兜底了。手写容易在
left 和 left 之间反复横跳，一不留神就死循环或越界。
它要求容器已排序（升序），且支持随机访问迭代器（
vector
、
array
可用，
list
不行） 返回第一个 ≥ 目标值的迭代器，没找到就返回
end()
，不用自己判空 内部用的是半开区间
[first, last)
，和绝大多数 STL 算法一致，不会因闭区间习惯出错 整数下标场景下，别直接用
int
算中点：
mid = (left + right) / 2
可能溢出；
std::lower_bound
内部用
std::distance
安全处理 手写二分时 mid 计算必须用 left + (right - left) / 2 不是为了“看起来高级”，是防止
left
和
right
都接近
INT_MAX
时加法溢出 —— 这种溢出不报错，但结果变成负数，后续下标访问直接 UB（未定义行为）。 错误写法：
mid = (left + right) / 2
正确写法：
mid = left + (right - left) / 2
如果用
size_t
或其他无符号类型，还得多一层检查：
right >= left
，否则
right - left
会回绕成极大正数 C++20 起可用
std::midpoint(left, right)
，它自动处理有/无符号、溢出、指针等所有情况 查找失败时返回什么值最容易引发逻辑 bug 很多人默认返回
-1
，但在无符号类型（如
size_t
）上下文中，
-1
会变成极大正数（如
18446744073709551615
），后续用作索引或比较时悄无声息地出错。 统一用有符号整型（如
int
）做返回值，或直接返回迭代器（推荐） 若必须返回下标，检查调用方是否可能将返回值赋给
size_t
：比如
auto idx = binary_search(...); vector.at(idx);
—— 这里
idx
是
-1
就崩了 更稳妥的做法是返回
std::optional
（C++17+），调用方必须显式判断是否有值 std::binary_search 只告诉你“在不在”，但你往往需要位置
std::binary_search
返回
bool
，适合纯存在性判断；但多数真实场景要的是下标、插入点或范围（比如找所有等于某值的元素）。 C知道 CSDN推出的一款AI技术问答工具 下载 立即学习 “ C++免费学习笔记（深入） ”； 要下标：用
std::lower_bound
，然后减去
begin()
得到索引 要插入位置（保持有序）：
std::lower_bound
的返回迭代器就是该插的位置 要找一段相等值：配合
std::upper_bound
，
[lower_bound, upper_bound)
就是完整区间 注意：三个函数都要求严格升序；如果容器是降序，得传
std::greater()
作为比较器，否则行为未定义 边界条件、迭代器有效性、类型符号性 —— 这些地方不写注释、不加断言、不测极端输入，上线后出问题根本看不出哪来的。

相关文章