lower_bound( )和upper_bound( )的基本用法_综合

lower_bound( )和upper_bound( )是C++ STL模板库中的函数，其作用可以看作是一个简单的二分模板。

基本使用方法：

lower_bound:

参数：lower_bound(首地址begin,末地址end+1,目标值)；
返回值：返回在指定区域内查找大于或等于目标值的第一个元素地址；
特殊情况：在指定区域内未找到大于或等于目标值的元素则返回末地址end+1。

upper_bound:

参数：upper_bound(首地址begin,末地址end+1,目标值)；
返回值：返回在指定区域内查找大于目标值的第一个元素地址；
特殊情况：在指定区域内未找到大于目标值的元素则返回末地址end+1。

适用条件：

在一有序序列中，快速查找一目标值。其时间复杂度为n*logn，可以处理1e5数量级的数据。

实例演示：

洛谷P1102

题目：A-B数对

题意：给出n个数字，从中找出符合A-B=C的数对个数。其中1≤n≤2×10⁵，A，B在长整型范围内。

思路：

? 我们先将n个数排序。

? 我们将A-B=C变化为A=B+C，所以只需要找到数组中的某个元素等于另一个元素+C等于A的情况数。

? 对于数组中第i个元素来说，a_i-1+C是一个确定的值，我们将其设置为目标值，lower_bound函数的作用是找出第一个大于等于目标值的数所在地址，upper_bound函数的作用是找出第一个大于目标值的数所在地址。由于数组的地址是连续的，所以我们将两个地址相减，就可以得到等于目标值的数的个数。即找到a_i+C的个数。

? 令B为数组元素a_i，令a_i+C为A，找到符合情况的个数。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N];
inline ll LintRead()
{
    char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){
    if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){
    s = s * 10 + ch - '0',ch = getchar();}return s * w;
}
int main()
{
    int c,n;ll ans=0;cin>>n>>c;for(int i=0;i<n;i++)a[i]=LintRead();//快读sort(a,a+n);for(int i=0;i<n;i++)ans+=(upper_bound(a,a+n,a[i]+c)-lower_bound(a,a+n,a[i]+c));//地址连续，可以直接相减cout<<ans;
}

lower_bound和upper_bound函数在结构体中的应用

两种形式：

1.比较函数的定义：

struct stu
{
    int w,v;
}
bool com(stu x,stu y)
{
    if(x.w!=y.w)return x.w<y.w;elsereturn x.v<y.v;
}stu a;//使用方法:
lower_bound(a+1,a+1+n,com);

2.结构体的构造

struct stu{
    int w,v;bool operator < (const stu &y) const{
    if(w!=y.w)return w<y.w;elsereturn v<y.v;}
};stu a;//使用方法:
upper_bound(a+1,a+1+n);

实例演示：

codeforces 699 div2 C题

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
typedef long long ll;
int t,a[M],b,c[M],n,m,ans[M];
struct A
{
    int x,b,index;
};
A d[M];
bool com(A xb,A yb)
{
    if(xb.x!=yb.x)return xb.x<yb.x;elsereturn xb.b<yb.b;
}
void fun(int cx)
{
    A *q;q=upper_bound(d+1,d+1+n,(A){
    cx,0,0},com);int h=upper_bound(d+1,d+1+n,(A){
    cx,0,0},com)-d;//通过地址的相对位置找到下标if((*(q-1)).x==cx){
    p.x=(*(q-1)).x;p.index=(*(q-1)).index;(*(q-1)).b=1;}else if((*q).x==cx&&h<=n)//注意判断是否超出范围{
    p.x=(*q).x;p.index=(*q).index;}
}
int main()
{
    cin>>t;while(t--){
    scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)scanf("%d",&a[i]);for(int i=1; i<=n; i++){
    scanf("%d",&b);d[i].x=b;if(b==a[i])d[i].b=1;elsed[i].b=0;d[i].index=i;}sort(d+1,d+1+n);//nlognfor(int i=1; i<=m; i++)scanf("%d",&c[i]);for(int i=1; i<=m; i++){
    p.x=-1;fun(c[i]);if(p.x!=-1)ans[i]=p.index;elseans[i]=0;}for(int i=m-1; i>=1; i--){
    if(ans[i]==0)ans[i]=ans[m];}bool bb=1;for(int i=1; i<=n; i++)if(d[i].b==0)bb=0;if(!bb||ans[m]==0){
    printf("NO\n");/*for(int i=1;i<m;i++)printf("%d ",ans[i]);printf("%d\n",ans[m]);*/}else{
    printf("YES\n");for(int i=1; i<m; i++)printf("%d ",ans[i]);printf("%d\n",ans[m]);}}
}