# lower_bound()用法
## **1、介绍**
lower_bound函数是C++ STL中一个强大的工具，适用于在有序序列中快速查找元素的位置。**用于在序列中查找第一个大于等于目标值的元素。**
正确使用lower_bound可以显著提高程序的效率，但在使用时应注意其适用条件和返回值处理，以避免潜在的问题。lower_bound本质上是通过二分查找实现的。
## **2、用法**
### **2.1 在vector中用法样例如下**
```cpp
#include <iostream>
#include <algorithm> // 包含lower_bound
#include <vector>    // 使用vector作为示例容器，但同样适用于原生数组
using namespace std;
int main() {
    // 使用vector作为示例，但同样适用于原生数组
    vector<int> arr = {1, 2, 4, 5, 7, 8, 10};
 
    int value = 5;
    auto it = lower_bound(arr.begin(), arr.end(), value);
 
    if (it != arr.end()) {
        cout << "Element found at index: " << (it - arr.begin()) << endl;
    } else {
        cout << "Element not found." << endl;
    }
 
    return 0;
}

```
在这个示例中，lower_bound函数将会返回指向元素5的迭代器，因为它是第一个大于或等于5的元素。 该示例会输出"3".

**注意事项：** 有序序列：使用lower_bound进行二分查找时，必须保证查找区间为升序序列。如果序列为降序，需要使用自定义的比较函数。
自定义比较：在某些情况下，我们可能需要基于特定的比较规则进行查找。lower_bound允许传入一个比较函数来实现自定义比较。例如，对于降序序列，可以使用greater<int>：
```cpp
#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;
}

```


### **2.2 在原生数组中用法样例如下**
如果你想在原生数组中使用lower_bound，你需要包含头文件<algorithm>和确保你的数组是已排序的。但是，原生数组没有.begin()和.end()成员函数，你需要传递指向数组的指针和数组的大小。这里是如何做的：
- 升序 
```cpp
#include <iostream>
#include <algorithm> // 包含lower_bound
using namespace std;
int main() {
    int arr[] = {1, 2, 4, 5, 7, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组元素数量
    int value = 5;
    auto it = lower_bound(arr, arr + n, value); // 使用指针和大小作为范围参数
 
    if (it != arr + n) { // 检查迭代器是否指向数组末尾之外的位置
        cout << "Element found at index: " << (it - arr) << endl;
    } else {
        cout << "Element not found." << endl;
    }
 
    return 0;
}
```

- 降序
```cpp
#include <iostream>
#include <algorithm> // 包含lower_bound
using namespace std;
int main() {
    int arr[] = {10, 7, 5, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组元素数量
    int value = 5;
    auto it = lower_bound(arr, arr + n, value, greater<int>()); // 使用指针和大小作为范围参数
 
    if (it != arr + n) { // 检查迭代器是否指向数组末尾之外的位置
        cout << "Element found at index: " << (it - arr) << endl;
    } else {
        cout << "Element not found." << endl;
    }
 
    return 0;
}

```


lower_bound返回的迭代器指向的是第一个不小于（即大于或等于）给定值的元素。如果所有元素都小于给定值，它将返回指向最后一个元素之后的位置（即end()迭代器）。因此，你需要检查返回的迭代器是否不等于end()来确定是否找到了元素。

对于原生数组，你需要手动计算数组的大小，并通过传递指向数组首元素的指针和指向数组尾元素下一个位置的指针来定义范围。对于容器（如vector、deque等），可以直接使用.begin()和.end()成员函数来定义范围。

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

# upper_bound()用法
**用于在序列中查找第一个大于目标值的元素。**

其他用法同lower_bound。