lower_bound与upper_bound在降序序列的应用

基本概念

lower_bound函数格式：lower_bound(起始地址，结束地址，要查找的数值）

upper_bound函数格式：upper_bound(起始地址，结束地址，要查找的数值）

lower_bound函数：返回第一个大于等于所要查找的数值的地址

upper_bound函数：返回第一个大于所要查找的数值的地址

返回值

设k为查找值。

对于升序或不下降序列，不填cmp函数：

upper_bound函数返回指向大于k的第一个元素的指针（迭代器），找不到就返回填入的区间右端点，也就是返回指向 | 区间末尾元素的后一个元素 | 的指针（迭代器）。

lower_bound函数返回指向大于等于k的第一个元素的指针（迭代器），找不到就返回填入的区间右端点，也就是返回指向 | 区间末尾元素的后一个元素 | 的指针（迭代器）。

对于降序或不上升序列，填cmp函数：

upper_bound函数返回指向小于k的第一个元素的指针（迭代器），找不到就返回填入的区间左端点，也就是返回指向区间初始元素的指针（迭代器）。

lower_bound函数返回指向小于等于k的第一个元素的指针（迭代器），找不到就返回填入的区间左端点，也就是返回指向区间初始元素的指针（迭代器）。

总结：如果找不到，总是返回最大值端的指针

代码

#include<bits/stdc++.h>
using namespace std;

int a[5]={1,2,3,4,5};
int b[5]={5,4,3,2,1};

bool cmp(const int &a,const int &b)
{
    return a>b;
}
 
int main()
{
    int c=lower_bound(a+0,a+5,3)-a;
    int c1=lower_bound(b+0,b+5,2,greater<int>())-b;    // 直接使用 greater<int>() 
    int c2=lower_bound(b+0,b+5,2,cmp)-b; // 自定义cmp改变比大小规则 
    cout<<c<<" "<<c1<<" "<<c2<<endl;// 两种方法得出的结果相同 
    return 0;
}