首页 > 代码库 > 二分查找

二分查找

2024-09-14 20:59:10   217人阅读

在升序中找到第一个>=key的值，同lower_bound

int lower_bound(int l,int r,int key) {    if(a[r]<key)return r+1;    while(l<r) {        int m=(l+r)/2;        if(a[m]<key)l=m+1;        else r=m;    //a[r]>=key    }    return r;}

在升序中找到第一个>key的值，同upper_bound

int upper_bound(int l,int r,int key){    if(a[r]<=key)return r+1;    while(l<r){        int m=(l+r)/2;        if(a[m]<=key)l=m+1;        else r=m;    //a[r]>key    }    return r;}

求最大化最小值或最小化最大值时，通过二分答案然后判断答案是否可行的方式求解

poj2456最大距离最小

题意：给出n个牛舍的坐标和c个牛，要求将牛放在牛舍并且使牛的距离尽量大，求最近牛的距离。
分析：二分距离d，然后判断牛是否可以按照距离d放置。

技术分享
 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=1e5; 5  6 int x[maxn+5]; 7 int n,c; 8  9 bool check(int d){10     int cnt=0;11     int j=1;12     for(int i=2;i<=n&&j<c;i++){13         cnt+=x[i]-x[i-1];14         if(cnt>=d)j++,cnt=0;15     }16     return j==c;17 }18 19 int upper_bound(int l,int r){//找到最后一个可行的下一个位置20     while(l<r){21         int m=(l+r)/2;22         if(check(m))l=m+1;23         else r=m;24     }25     return r;26 }27 28 int main(){29     scanf("%d%d",&n,&c);30     for(int i=1;i<=n;i++)scanf("%d",&x[i]);31 32     sort(x+1,x+1+n);33     printf("%d\n",upper_bound(0,1e9)-1);34 }
View Code

查询区间[l,r]中从左往右第一个小于key的值的下标

区间左端点固定，右端点向右移动，该区间最小值是非增序列，所以类似lower_bound来找小于key的最左边的值，其中区间最小值用rmq做到O(1)查询

技术分享
 1 const int maxn=100000; 2  3 int n; 4 int a[maxn+5]; 5 int minv[maxn+5][32]; 6  7 void rmq(){ 8     for(int i=1;i<=n;i++)minv[i][0]=a[i]; 9 10     for(int j=1;(1<<j)<=n;j++){11         for(int i=1;i+(1<<j)<=n+1;i++){12             minv[i][j]=min(minv[i][j-1],minv[i+(1<<(j-1))][j-1]);13         }14     }15 }16 17 int query(int l,int r){18     int k=0;19     while((1<<(k+1))<=r-l+1)k++;20     return min(minv[l][k],minv[r-(1<<k)+1][k]);21 }22 23 int lower_bound(int l,int r,int key){//第一个小于等于key的下标24     if(query(l,r)>key)return r+1;25     while(l<r){26         int m=(l+r)/2;27         if(query(l,m)<=key)r=m;28         else l=m+1;29     }30     return r;31 }
View Code

hdu5875Function区间取模

题意：给出一个长为100000的序列，和区间[l,r]求 技术分享
分析：对比自己大的数取模等于自己，将从左向右依次取模的结果保存在ans中，然后寻找右边第一个小于等于ans的值，一个数x对小于x的值最多取模logx次就会变成0，所以复杂度为O(mlognlogn)
主程序如下：

技术分享
 1 #include<bits/stdc++.h> 2 using namespace std; 3  4 int work(int l,int r){ 5     int ans=a[l];l++; 6     while(l<=r&&ans){ 7         int k=lower_bound(l,r,ans);//第一个小于等于ans的下标 8         if(k<=r)ans%=a[k]; 9         l=k+1;10     }11     return ans;12 }13 14 int main(){15     int T;scanf("%d",&T);16     while(T--){17         scanf("%d",&n);18         for(int i=1;i<=n;i++)scanf("%d",&a[i]);19         rmq();20         int m;scanf("%d",&m);21         while(m--){22             int l,r;scanf("%d%d",&l,&r);23             printf("%d\n",work(l,r));24         }25     }26 }
View Code

 

二分查找


联系
我们