lower_bound和upper_bound多功能自定义
发布时间：
两个二分函数自定义对于结构体的二分查找，还有官方的自定义比较函数。
lower_bound() 有两种形式：
lower_bound (first, last, val);（无自定义比较）lower_bound (first, last, val, Compare comp);（自定义比较）
在有序的前提下，lower_bound 返回指向第一个值不小于 val 的位置，也就是返回第一个大于等于 val 的值的位置。（通过二分查找，\(O(log_2n)\) 的复杂度）。
注意：如果没有大于等于 val 的元素，会指向末尾元素的下一个。
无自定义比较使用
- STL的使用方式
vector<int> v={2,3,4,5,6};
vector<int>::iterator it;
it=lower_bound(v.begin(),v.end(),3);
cout<<(*it)<<endl;//(*it)为对应的值
cout<<v[it-v.begin()];//it-v.begin()为第几个元素（从0开始）
//如果元素全部小于 val ,则 it=v.end()
- 数组的使用方式
int a[100],n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int x=lower_bound(a+1,a+n+1,3)-a;//不论从0开始，还是从1开始，都只-数组名
cout<<a[x]<<endl;//x为对应下标
//如果元素全部小于 val ,则 x=n+1
- 自定义查找使用
- 返回第一个 false 的元素，val 是自定义函数的第二个参数
- 前提是有序（从左往右=从满足 cmp 到不满足 cmp 的单调性），不然会按照折半来查找，可能得到的不是第一个满足条件的
bool cmp(int e,int val){
return e>=val;
}
int main(){
int a[100],n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int x=lower_bound(a+1,a+n+1,3,cmp)-a;
//找到的是第一个小于3的元素
cout<<x<<endl;
return 0;
}
- 官方的比较函数
lower_bound( begin , end , val , less<type>() )
//加入了less<type>()比较函数：适用于从小到大排序的有序序列，
//查找第一个大于等于 val 的数字
lower_bound( begin , end , val , greater<type>() )
//加入了greater<type>()比较函数：适用于从小到大排序的有序序列，
//查找第一个小于等于 val 的数字
- 结构体二分查找
struct Student{
int _id; //学号
int _num; //排名
Student(int id, int num)
:_id(id), _num(num)
{}
}Stu;
struct CompareV
{
bool operator() (const Stu& s1, const Stu& s2)// 排名升序
{
return s1._num < s2._num;
}
};
int main()
{
vector<Stu> vS = { { 101, 34 }, { 103, 39 }, { 102, 35 } };
//CompareV()排完序后是这个样子
//101 34
//102 35
//103 39
auto iter = lower_bound(vS.begin(), vS.end(), Stu(200,33), CompareV());
cout << iter - vS.begin() << endl; //我们就找到了按仿函数排序(找排名比33大的位置 就是0）
}
| lower_bound | upper_bound | |
|---|---|---|
| 无比较函数 | 返回第一个 >=x 的元素 | 返回第一个 >x 的元素 |
| 有比较函数 | 返回第一个 false 的元素 | 返回第一个 true 的元素 |
发表评论