C++二分查找向上和向下的函数是什么
时间: 2024-04-17 21:23:58 浏览: 15
C++中的二分查找向上和向下分别可以使用`std::lower_bound`和`std::upper_bound`函数来实现。
`std::lower_bound`函数用于在有序序列中查找第一个大于等于给定值的元素,并返回该元素的迭代器。函数的原型如下:
```cpp
template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);
```
`std::upper_bound`函数用于在有序序列中查找第一个大于给定值的元素,并返回该元素的迭代器。函数的原型如下:
```cpp
template <class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);
```
这两个函数需要传入一个有序序列的起始迭代器和结束迭代器,以及要查找的值。它们返回的迭代器指向序列中满足条件的元素。
注意:使用这两个函数之前,需要确保序列已经按照升序进行排序。
以下是一个示例代码,演示了如何使用这两个函数进行二分查找:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> nums = {1, 2, 3, 4, 4, 5, 6, 7};
int target = 4;
auto lower = std::lower_bound(nums.begin(), nums.end(), target);
auto upper = std::upper_bound(nums.begin(), nums.end(), target);
std::cout << "Lower bound: " << *lower << std::endl;
std::cout << "Upper bound: " << *upper << std::endl;
return 0;
}
```
输出结果为:
```
Lower bound: 4
Upper bound: 5
```
这表示在有序序列中,第一个大于等于4的元素是4,第一个大于4的元素是5。