二分查找在有序数组中高效定位目标值，C++提供binary_search和lower_bound两个函数。binary_search返回布尔值判断目标值是否存在，lower_bound返回第一个大于等于目标值的迭代器，可用于获取插入位置或实际索引。两者均需数据有序，时间复杂度为O(log n)，其中lower_bound更灵活，适用于更多场景。降序时需传入greater()等自定义比较函数。掌握这两个函数可显著提升处理有序数据的效率。
二分查找是一种在有序数组中快速定位目标值的高效算法，时间复杂度为 O(log n)。C++ 提供了两种常用的内置函数来实现二分查找：binary_search 和 lower_bound。它们都定义在 gorithm> 头文件中，适用于已排序的容器或数组。
C++ binary_search 用法
binary_search 用于判断某个值是否存在于有序区间中，返回一个布尔值（true 或 false）。
函数原型：
std::binary_search(起始迭代器, 结束迭代器, 目标值)
注意：容器必须是升序排列（默认），若为降序需自定义比较函数。
立即学习“C++免费学习笔记（深入）”；
示例代码：
#include
#include
#include iostream>
using namespace std;
int main() {
vector nums = {1, 3, 5, 7, 9};
bool found = binary_search(nums.begin(), nums.end(), 5); // true
cout return 0;
}
C++ lower_bound 用法
lower_bound 返回第一个大于等于目标值的元素的迭代器。如果所有元素都小于目标值，则返回 end()。
函数原型：
std::lower_bound(起始迭代器, 结束迭代器, 目标值)
常用于获取插入位置或查找首个不小于某值的位置。
示例代码：
vector nums = {1, 3, 5, 7, 9};
auto it = lower_bound(nums.begin(), nums.end(), 6);
cout
获取索引方式：
int index = lower_bound(nums.begin(), nums.end(), 6) – nums.begin(); // index = 3
binary_search 与 lower_bound 的区别
• 返回类型不同：binary_search 返回 bool；lower_bound 返回迭代器。
• 用途不同：binary_search 只判断是否存在；lower_bound 可获取位置，适合插入、去重等场景。
• 性能差异小：两者时间复杂度相同，但 lower_bound 更灵活。
例如，在需要判断存在性并获取位置时，直接使用 lower_bound 更高效，避免两次遍历。
自定义比较函数（如降序数组）
若数组为降序，需传入比较函数 greater()
vector nums = {9, 7, 5, 3, 1}; // 降序
bool found = binary_search(nums.begin(), nums.end(), 5, greater());
auto it = lower_bound(nums.begin(), nums.end(), 6, greater()); // 找第一个 ≤6 的位置
基本上就这些。掌握 binary_search 和 lower_bound 能大幅提升编码效率，尤其在处理有序数据时非常实用。注意使用前确保数据有序，否则结果未定义。不复杂但容易忽略。
以上就是C++如何实现二分查找_C++ binary_search与lower_bound用法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1487032.html
微信扫一扫 
支付宝扫一扫 
