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

C++ STL常用二分查找算法

news 2025/6/16 11:30:29

lower_bound

lower_bound 是 C++ 标准库算法，通常用于有序序列中查找第一个不小于给定值的元素。它属于 <algorithm> 头文件，并且是基于二分查找实现的，因此要求输入序列必须是有序的。

基本语法

#include <algorithm>  // 引入算法库Iterator lower_bound(Iterator first, Iterator last, const T& value);

first 和 last 是迭代器，分别表示容器的起始位置和结束位置（不包括 last）。
value 是要在容器中查找的目标值。
返回值是迭代器，指向第一个不小于 value 的元素。如果没有找到符合条件的元素，返回 last。

使用条件

容器中的元素必须是有序的，通常是按非递减顺序（从小到大）排列的。
如果容器无序，需要先对容器进行排序，才能使用 lower_bound。

返回值解释

如果找到一个元素，其值不小于 value，返回指向该元素的迭代器。
如果所有元素都小于 value，返回 last，即容器的末尾。

示例代码

示例 1：简单查找

#include <iostream>
#include <vector>
#include <algorithm>  // 需要引入algorithmint main() {std::vector<int> v = {1, 2, 4, 4, 5, 8, 10};int value = 4;auto it = std::lower_bound(v.begin(), v.end(), value);if (it != v.end()) {std::cout << "第一个不小于 " << value << " 的元素是: " << *it << std::endl;} else {std::cout << "没有找到不小于 " << value << " 的元素。" << std::endl;}return 0;
}

输出：

第一个不小于 4 的元素是: 4

在这个例子中，lower_bound 返回了指向值为 4 的第一个元素的迭代器。

示例 2：未找到的情况

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> v = {1, 2, 4, 4, 5, 8, 10};int value = 12;auto it = std::lower_bound(v.begin(), v.end(), value);if (it != v.end()) {std::cout << "第一个不小于 " << value << " 的元素是: " << *it << std::endl;} else {std::cout << "没有找到不小于 " << value << " 的元素。" << std::endl;}return 0;
}

输出：

没有找到不小于 12 的元素。

因为所有元素都小于 12，所以返回 v.end()。

注意事项

容器必须有序：如果容器未排序，lower_bound 的结果是未定义的。
时间复杂度：由于使用二分查找，时间复杂度为 O(logn)，其中 n 是容器中元素的数量。
自定义比较函数：如果需要使用自定义的顺序规则，可以提供一个比较函数作为参数，例如
```
auto it = std::lower_bound(v.begin(), v.end(), value, custom_compare);
```
其中 custom_compare 是一个函数对象，接收两个元素作为参数，返回一个布尔值，用于定义排序规则。

lower_bound 是一个非常实用的函数，特别适合在有序数据中进行高效的查找操作。

upper_bound

upper_bound 是 C++ 标准库中的一个算法函数，与 lower_bound 类似，它也用于有序序列中查找特定值的位置，但功能略有不同。upper_bound 用于查找第一个大于给定值的元素的位置。它同样基于二分查找实现，因此要求输入序列必须是有序的。

基本语法

#include <algorithm>  // 引入算法库Iterator upper_bound(Iterator first, Iterator last, const T& value);

first 和 last 是迭代器，分别表示容器的起始位置和结束位置（不包括 last）。
value 是要在容器中查找的目标值。
返回值是迭代器，指向第一个大于 value 的元素。如果没有找到符合条件的元素，返回 last。

使用条件

容器中的元素必须是有序的，通常是按非递减顺序（从小到大）排列的。
如果容器无序，需要先对容器进行排序，才能使用 upper_bound。

返回值解释

如果找到一个元素，其值大于 value，返回指向该元素的迭代器。
如果所有元素都小于或等于 value，返回 last，即容器的末尾。

示例代码

示例 1：简单查找

#include <iostream>
#include <vector>
#include <algorithm>  // 需要引入algorithmint main() {std::vector<int> v = {1, 2, 4, 4, 5, 8, 10};int value = 4;auto it = std::upper_bound(v.begin(), v.end(), value);if (it != v.end()) {std::cout << "第一个大于 " << value << " 的元素是: " << *it << std::endl;} else {std::cout << "没有找到大于 " << value << " 的元素。" << std::endl;}return 0;
}

输出：

第一个大于 4 的元素是: 5

在这个例子中，upper_bound 返回了指向值为 5 的元素的迭代器。

示例 2：未找到的情况

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> v = {1, 2, 4, 4, 5, 8, 10};int value = 12;auto it = std::upper_bound(v.begin(), v.end(), value);if (it != v.end()) {std::cout << "第一个大于 " << value << " 的元素是: " << *it << std::endl;} else {std::cout << "没有找到大于 " << value << " 的元素。" << std::endl;}return 0;
}

输出：

没有找到大于 12 的元素。

因为所有元素都小于或等于 12，所以返回 v.end()。

注意事项

容器必须有序：如果容器未排序，upper_bound 的结果是未定义的。
时间复杂度：由于使用二分查找，时间复杂度为 O(logn)，其中 n 是容器中元素的数量。
自定义比较函数：如果需要使用自定义的顺序规则，可以提供一个比较函数作为参数，例如
```
auto it = std::upper_bound(v.begin(), v.end(), value, custom_compare);
```
其中 custom_compare 是一个函数对象，接收两个元素作为参数，返回一个布尔值，用于定义排序规则。
与 lower_bound 的区别：
- lower_bound 返回第一个不小于给定值的元素。
- upper_bound 返回第一个大于给定值的元素。
- 如果容器中存在多个相同的值，lower_bound 会返回第一个等于该值的元素，而 upper_bound 会返回第一个大于该值的元素。