C++如何实现二分查找_C++ binary_search与lower_bound用法

二分查找在有序数组中高效定位目标值，C++提供binary_search和lower_bound两个函数。binary_search返回布尔值判断目标值是否存在，lower_bound返回第一个大于等于目标值的迭代器，可用于获取插入位置或实际索引。两者均需数据有序，时间复杂度为O(log n)，其中lower_bound更灵活，适用于更多场景。降序时需传入greater<int>()等自定义比较函数。掌握这两个函数可显著提升处理有序数据的效率。

二分查找是一种在有序数组中快速定位目标值的高效算法，时间复杂度为 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()。

人民网AIGC-X

国内科研机构联合推出的AI生成内容检测工具

下载

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 能大幅提升编码效率，尤其在处理有序数据时非常实用。注意使用前确保数据有序，否则结果未定义。不复杂但容易忽略。