文章目录
1）概述
- l o w e r _ b o u n d ( ) lower\_bound() lower_bound() 和 u p p e r _ b o u n d ( ) upper\_bound() upper_bound() 都是基于二分查找在一个排好序的数组或容器（如 v e c t o r , l i s t , s e t vector,\ list,\ set vector, list, set ）中进行快速查找的函数，位于 < a l g o r i t h m > <algorithm> <algorithm> 标准库中，由于采用二分查找，所以函数的时间复杂度是 O ( l o g 2 n ) O(log_2^n) O(log2n)
- 划重点！基于二分查找！数组或容器必须有序！
2）函数使用
-
l o w e r _ b o u n d ( b e g i n , e n d , n u m ) lower\_bound(begin,end,num) lower_bound(begin,end,num)：适用于从小到大排序的有序序列，从数组/容器的 b e g i n begin begin 位置起，到 e n d − 1 end-1 end−1 位置结束，查找第一个大于等于 n u m num num 的数字
- 若找到则返回该数字的地址，通过减去起始地址 b e g i n begin begin 的技巧可以求得其在数组/容器中的下标，如 l o w e r _ b o u n d ( a r r , a r r + n , 3 ) − a r r lower\_bound(arr,arr+n,3)-arr lower_bound(arr,arr+n,3)−arr 表示在数组 a r r arr arr 中查找第一个大于等于 3 3 3 的元素在数组中的下标
- 若找不到，则返回 e n d end end，即数组/容器最后一个元素的下一个元素
-
u p p e r _ b o u n d ( b e g i n , e n d , n u m ) upper\_bound(begin,end,num) upper_bound(begin,end,num)：适用于从小到大排序的有序序列，从数组/容器的 b e g i n begin begin 位置起，到 e n d − 1 end-1 end−1 位置结束，查找第一个大于 n u m num num 的数字
-
若找到则返回该数字的地址，通过减去起始地址 b e g i n begin begin 的技巧可以求得其在数组/容器中的下标，如 u p p e r _ b o u n d ( a r r , a r r + n , 3 ) − a r r upper\_bound(arr,arr+n,3)-arr upper_bound(arr,arr+n,3)−arr 表示在数组 a r r arr arr 中查找第一个大于 3 3 3 的元素在数组中的下标
-
若找不到，则返回 e n d end end，即数组/容器最后一个元素的下一个元素
-
-
l o w e r _ b o u n d ( b e g i n , e n d , n u m , g r e a t e r < t y p e > ( ) ) lower\_bound(begin,end,num,greater<type>()) lower_bound(begin,end,num,greater<type>())：适用于从大到小排序的有序序列，从数组/容器的 b e g i n begin begin 位置起，到 e n d − 1 end-1 end−1 位置结束，查找第一个小于等于 n u m num num 的数字
- 若找到则返回该数字的地址，通过减去起始地址 b e g i n begin begin 的技巧可以求得其在数组/容器中的下标，如 l o w e r _ b o u n d ( a r r , a r r + n , 3 , g r e a t e r < i n t > ( ) ) − a r r lower\_bound(arr,arr+n,3,greater<int>())-arr lower_bound(arr,arr+n,3,greater<int>())−arr 表示在数组 a r r arr arr 中查找第一个小于等于 3 3 3 的元素在数组中的下标
- 若找不到，则返回 e n d end end，即数组/容器最后一个元素的下一个元素
-
u p p e r _ b o u n d ( b e g i n , e n d , n u m , g r e a t e r < t y p e > ( ) ) upper\_bound(begin,end,num,greater<type>()) upper_bound(begin,end,num,greater<type>())：适用于从大到小排序的有序序列，从数组/容器的 b e g i n begin begin 位置起，到 e n d − 1 end-1 end−1 位置结束，查找第一个小于 n u m num num 的数字
-
若找到则返回该数字的地址，通过减去起始地址 b e g i n begin begin 的技巧可以求得其在数组/容器中的下标，如 u p p e r _ b o u n d ( a r r , a r r + n , 3 , g r e a t e r < i n t > ( ) ) − a r r upper\_bound(arr,arr+n,3,greater<int>())-arr upper_bound(arr,arr+n,3,greater<int>())−arr 表示在数组 a r r arr arr 中查找第一个小于 3 3 3 的元素在数组中的下标
-
若找不到，则返回 e n d end end，即数组/容器最后一个元素的下一个元素
-
3）案例代码
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
// 解题思路:
const int N=1e5+5;
int main() {
// 升序
int arr[]={1,3,2,8,5};
sort(arr,arr+5);
cout<<"序列为(从小到大排序):";
for(auto x:arr) cout<<x<<' ';
cout<<endl;
// 1.lower_bound
cout<<lower_bound(arr,arr+5,5)-arr<<endl; // 第一个大于等于5的是5,下标是3
// 2.upper_bound
cout<<upper_bound(arr,arr+5,6)-arr<<endl; // 第一个大于6的是8,下标是4
// 降序
sort(arr,arr+5,greater<int>()); // greater<int>()表示降序规则
cout<<"序列为(从大到小排序):";
for(auto x:arr) cout<<x<<' ';
cout<<endl;
// 3.lower_bound
cout<<lower_bound(arr,arr+5,3,greater<int>())-arr<<endl; // 第一个小于等于3的是3,下标是2
// 4.upper_bound
cout<<upper_bound(arr,arr+5,3,greater<int>())-arr<<endl; // 第一个小于等于3的是2,下标是3
return 0;
}