cpp的stl二分查找库函数
C++ 标准模板库（STL）提供了多个用于二分查找的函数，这些函数定义在 `<algorithm>` 头文件中。它们适用于已排序的序列（如数组、`vector` 等），能够高效地查找元素或插入位置。
以下是 C++ STL 中常用的二分查找函数及其用法：
---
### 1. **`std::lower_bound`**
- **功能**：返回第一个 **大于或等于** 目标值的元素的迭代器。
- **适用场景**：查找第一个不小于目标值的位置。
- **时间复杂度**：O(log n)。
**函数原型**：
**示例**：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {1, 3, 5, 7, 9};
int target = 6;
// 查找第一个 >= target 的元素
auto it = lower_bound(nums.begin(), nums.end(), target);
if (it != nums.end()) {
cout << "第一个大于或等于 " << target << " 的元素是: " << *it << endl;
} else {
cout << "没有找到大于或等于 " << target << " 的元素" << endl;
}
return 0;
}
```
**输出**：
```
第一个大于或等于 6 的元素是: 7
```
---
### 2. **`std::upper_bound`**
- **功能**：返回第一个 **大于** 目标值的元素的迭代器。
- **适用场景**：查找第一个大于目标值的位置。
- **时间复杂度**：O(log n)。
**示例**：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {1, 3, 5, 7, 9};
int target = 6;
// 查找第一个 > target 的元素
auto it = upper_bound(nums.begin(), nums.end(), target);
if (it != nums.end()) {
cout << "第一个大于 " << target << " 的元素是: " << *it << endl;
} else {
cout << "没有找到大于 " << target << " 的元素" << endl;
}
return 0;
}
```
**输出**：
```
第一个大于 6 的元素是: 7
```
---
3. **`std::binary_search`**
- **功能**：检查目标值是否存在于序列中。
- **适用场景**：判断元素是否存在。
- **时间复杂度**：O(log n)。
**示例**：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {1, 3, 5, 7, 9};
int target = 5;
// 检查 target 是否存在
bool exists = binary_search(nums.begin(), nums.end(), target);
if (exists) {
cout << target << " 存在于数组中" << endl;
} else {
cout << target << " 不存在于数组中" << endl;
}
return 0;
}
```
**输出**：
```
5 存在于数组中
```
---
### 4. **`std::equal_range`**
- **功能**：返回一个范围，表示所有等于目标值的元素区间（通过 `std::pair` 返回 `lower_bound` 和 `upper_bound` 的结果）。
- **适用场景**：查找目标值的所有出现位置。
- **时间复杂度**：O(log n)。
**函数原型**：
```cpp
template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);
```
**示例**：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {1, 3, 5, 5, 5, 7, 9};
int target = 5;
// 查找所有等于 target 的元素范围
auto range = equal_range(nums.begin(), nums.end(), target);
cout << "等于 " << target << " 的元素范围是: ["
<< distance(nums.begin(), range.first) << ", "
<< distance(nums.begin(), range.second) << ")" << endl;
return 0;
}
```
**输出**：
```
等于 5 的元素范围是: [2, 5)
```
---
### 5. **综合示例**
以下是一个综合使用上述函数的示例：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {1, 3, 5, 5, 5, 7, 9};
int target = 5;
// 使用 binary_search 检查是否存在
bool exists = binary_search(nums.begin(), nums.end(), target);
cout << target << " 是否存在: " << (exists ? "是" : "否") << endl;
// 使用 lower_bound 查找第一个 >= target 的元素
auto lower = lower_bound(nums.begin(), nums.end(), target);
cout << "第一个大于或等于 " << target << " 的元素是: " << *lower << endl;
// 使用 upper_bound 查找第一个 > target 的元素
auto upper = upper_bound(nums.begin(), nums.end(), target);
cout << "第一个大于 " << target << " 的元素是: " << *upper << endl;
// 使用 equal_range 查找所有等于 target 的元素范围
auto range = equal_range(nums.begin(), nums.end(), target);
cout << "等于 " << target << " 的元素范围是: ["
<< distance(nums.begin(), range.first) << ", "
<< distance(nums.begin(), range.second) << ")" << endl;
return 0;
}
```
**输出**：
```
5 是否存在: 是
第一个大于或等于 5 的元素是: 5
第一个大于 5 的元素是: 7
等于 5 的元素范围是: [2, 5)
```
---
### 总结
C++ STL 中的二分查找函数非常强大且高效，适用于已排序的序列。通过掌握这些函数，可以轻松解决查找、插入位置等问题。