About STL 中的 lower_bound

concert_B · 2024-03-21 10:52:24 · 算法·理论

lower_bound 用法

数组

周知所众，在 <algorithm> 库中有两个函数 lower_bound 和 upper_bound，用于在一个有序的数组中二分查找。

升序：

• lower_bound(begin,end,num)：从数组的 begin 位置到 end-1 位置二分查找第一个大于或等于 num 的数字，找到返回该数字的地址，不存在则返回 end。

• upper_bound(begin,end,num)：从数组的 begin 位置到 end-1 位置二分查找第一个大于 num 的数字，找到返回该数字的地址，不存在则返回 end。

降序：

• 如果想找第一个小于或等于 num 的数字，可以使用 lower_bound(begin,end,num,greater<type>())，其中 type 是该数组的类型。

• 同理，upper_bound(begin,end,num,greater<type>()) 可以找到第一个小于 num 的数字。

通过返回的地址减去起始地址 begin，可以得到找到数字在数组中的下标。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[5]={1,4,6,6,9};
int b[5]={9,6,3,3,1};
signed main(){
    cout<<lower_bound(a,a+5,6)-a<<endl;
    cout<<upper_bound(a,a+5,6)-a<<endl;
    cout<<lower_bound(b,b+5,3,greater<int>())-b<<endl;
    cout<<upper_bound(b,b+5,3,greater<int>())-b;
    return 0;
}

输出

2
4
2
4

vector

vector 本质与数组相似，用法基本相同。

升序：

• lower_bound(a.begin(),a.end(),num)：从数组的 a.begin() 位置到 a.end()-1 位置二分查找第一个大于或等于 num 的数字，找到返回该数字的地址，不存在则返回 a.end()。

• upper_bound(a.begin(),a.end(),num)：从数组的 a.begin() 位置到 a.end()-1 位置二分查找第一个大于 num 的数字，找到返回该数字的地址，不存在则返回 a.end()。

降序：

• 如果想找第一个小于或等于 num 的数字，可以使用 lower_bound(a.begin(),a.end(),num,greater<type>())，其中 type 是该 vector 的类型。

• 同理，upper_bound(a.begin(),a.end(),num,greater<type>()) 可以找到第一个小于 num 的数字。

通过返回的地址减去起始地址 a.begin()，可以得到找到数字在 vector 中的下标。

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> a,b;
signed main(){
    a.push_back(1);a.push_back(4);a.push_back(6);a.push_back(6);a.push_back(9);
    b.push_back(9);b.push_back(6);b.push_back(3);b.push_back(3);b.push_back(1);
    cout<<lower_bound(a.begin(),a.end(),6)-a.begin()<<endl;
    cout<<upper_bound(a.begin(),a.end(),6)-a.begin()<<endl;
    cout<<lower_bound(b.begin(),b.end(),3,greater<int>())-b.begin()<<endl;
    cout<<upper_bound(b.begin(),b.end(),3,greater<int>())-b.begin();
    return 0;
}

输出

2
4
2
4

set

set 中的 lower_bound 是内置的，语法与数组完全不同。

返回值是 set<type>::iterator 类型的，是第一个大于或等于 num 的数字的迭代器。

由于 set 不是线性的，所以不可以减去起始地址 a.begin()，来得到数字在 set 中的下标。

况且 set 也不是数组。

#include<bits/stdc++.h>
#define int long long
using namespace std;
set<int> a;
signed main(){
    a.insert(1);a.insert(4);a.insert(6);a.insert(6);a.insert(9);
    cout<<*a.lower_bound(6)<<endl;
    return 0;
}

输出

6

map

map 中的 lower_bound 与 set 类似。

返回值是 map<type>::iterator 类型的，是第一个大于或等于第一关键字 num 的数字的迭代器。

由于 map 不是线性的，所以不可以减去起始地址 a.begin()，来得到数字在 map 中的下标。

#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int,int> a;
signed main(){
    a[1]=1;a[2]=4;a[4]=6;a[5]=6;a[6]=9;
    cout<<a.lower_bound(3)->second<<endl;
    return 0;
}

输出

6