文章目录
- 参考代码
- 二分标准模板
题目来源-洛谷网
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int m,n,a[N],b;
int find(int t)
{int l=1,r=n;while(l<r){int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) r=mid;//中间值比查找的值大或者相等,区间左移 else l=mid+1; }if(a[l]==t) return r; //此时 l=r 都是要求的值 else return -1;
}
int main()
{int ans;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>b;ans=find(b);cout<<ans<<" ";}return 0;
}
如果要求的是输出编号的最大值
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int m,n,a[N],b;
int ans;
int find(int t)
{int l=1,r=n;while(l<r){int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]<=t) l=mid+1;//中间值比查找的值大或者相等,区间左移 else r=mid; }if(a[l-1]==t) return l-1; //区间在右移 ,右端的值不会满足条件 else return -1;
}
int main()
{int ans;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>b;ans=find(b);cout<<ans<<" ";}return 0;
}
万能公式套用版
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int m,n,a[N],b;
int ans;
int find(int t)
{int l=1,r=n;while(l<=r) //再求最小编号时,l r相邻 比如 133 一定要注意最小编号是否能拿到 {int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) {ans = mid; //记录值 r=mid-1; }else l=mid+1;}if(a[ans]==t) return ans; else return -1;
}
int main()
{int ans;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>b;ans=find(b);cout<<ans<<" ";}return 0;
}
二分标准模板
int find(int t)
{int l=1,r=n;while(l<=r) //一定是相等{int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) {ans = mid; //记录值 r=mid-1; }else l=mid+1;}if(a[ans]==t) return ans; else return -1;
}
求较小编号
int find(int t)
{int l=1,r=n;while(l<r) {int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) {r=mid; }else l=mid+1;}if(a[r]==t) return r; //l也对else return -1;
}
求较大编号
int find(int t)
{int l=1,r=n;while(l<r) {int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]<=t) {l=mid+1;}else r=mid; }if(a[l-1]==t) return l-1; //l会比准确值大些else return -1;
}