当前位置：首页 > news >正文

C++中的lower_bound函数详解

news 来源：原创 2024/9/29 8:20:00

在C++标准库中，lower_bound函数是一个非常有用的工具，它通过二分查找算法在有序序列中定位第一个大于或等于给定值的元素的位置。本文将详细介绍lower_bound函数的使用方法、注意事项以及性能特点。

函数原型与基本用法

lower_bound函数定义在头文件中，其原型如下：

template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);

其中，first和last是表示要搜索的有序序列的迭代器范围（前闭后开区间[first, last)），value是要查找的值。函数返回一个迭代器，指向第一个大于或等于value的元素位置。如果找不到这样的元素，则返回last。

下面是一个简单的使用示例：

#include <iostream>
#include <algorithm>
#include <vector>int main() {std::vector<int> vec = {1, 3, 5, 7, 9};// 查找第一个大于等于6的元素位置auto it = std::lower_bound(vec.begin(), vec.end(), 6);if (it != vec.end()) {std::cout << "第一个大于等于6的元素位置："<< std::distance(vec.begin(), it) << std::endl;} else {std::cout << "未找到大于等于6的元素" << std::endl;}return 0;
}

在这个示例中，lower_bound函数将会返回指向元素7的迭代器，因为它是第一个大于或等于6的元素。

使用条件与注意事项

有序序列：使用lower_bound进行二分查找时，必须保证查找区间为升序序列。如果序列为降序，需要使用自定义的比较函数。
自定义比较：在某些情况下，我们可能需要基于特定的比较规则进行查找。lower_bound允许传入一个比较函数来实现自定义比较。例如，对于降序序列，可以使用std::greater<int>：

#include <iostream>
#include <algorithm>
#include <vector>int main() {std::vector<int> vec = {9, 7, 5, 3, 1};// 查找第一个大于等于6的元素位置（降序）auto it = std::lower_bound(vec.begin(), vec.end(), 6, std::greater<int>());if (it != vec.end()) {std::cout << "第一个大于等于6的元素位置（从后往前数）："<< std::distance(it, vec.end()) << std::endl;} else {std::cout << "未找到大于等于6的元素" << std::endl;}return 0;
}

返回值处理：如果lower_bound未找到目标元素，它会返回last的地址，此时需要注意检查返回值是否等于end()，以避免对越界地址进行解引用。

性能特点

lower_bound函数的算法复杂度为 $O (l o g n)$ ，其中 $n$ 是序列的元素个数。这使得它在处理大规模数据时非常高效。然而，对于关联容器（如std::set和std::map），虽然也可以使用lower_bound，但由于关联容器不支持随机访问，其性能可能退化到 $O (n)$ 。因此，在使用关联容器时，建议使用容器自带的lower_bound成员函数，它们通常经过优化，可以提供更好的性能。