1.元素编号
输入 n 个单调不减的(就是后面的数字不小于前面的数字)非负整数a1,a2,…,an,然后进行 m 次询问。对于每次询问,给出一个整数 q,要求输出数列中第一个大于等于q的数字的编号。(若未找到则默认输出-1)
输入共 3 行:
第 1 行,2 个整数 n 和 m,表示数字个数和询问次数;
第 2 行,n 个整数,表示这些待查询的数字;
第 3 行,m 个整数,表示询问这些数字的编号,从 1 开始编号。
输出共 1 行:
m 个空格隔开的整数表示答案。
1≤n≤106;0≤a1≤a2≤⋅⋅⋅≤an≤109;0≤q≤109;0≤m≤105。
AC代码如下:
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=m;i++)
{
int q;
cin >> q;
int l=1,r=n,ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(a[mid]>=q)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
cout << ans << " ";
}
return 0;
}
1.1元素编号(lower_bound)
题目同上一题,解法不同用了STL库里的lower_bound函数
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=m;i++)
{
int q;
cin >> q;
int x=lower_bound(a+1,a+n+1,q)-a;
cout << x << " ";
}
return 0;
}
2.值查找
输入 n 个单调不减的(就是后面的数字不小于前面的数字)非负整数a1,a2,…,an,然后进行 m 次询问。对于每次询问,给出一个整数 q,要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出 -1 。
输入共 3 行:
第 1 行,2 个整数 n 和 m,表示数字个数和询问次数;
第 2 行,n 个整数,表示这些待查询的数字;
第 3 行,m 个整数,表示询问这些数字的编号,从 1 开始编号。
输出共 1 行:
m 个空格隔开的整数表示答案。
1≤n≤106;0≤a1≤a2≤⋅⋅⋅≤an≤109;0≤q≤109;0≤m≤105 。
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=m;i++)
{
int q;
cin >> q;
int x=lower_bound(a+1,a+n+1,q)-a;
if(a[x]==q)
{
cout << x << " ";
}
else cout << -1 << " ";
}
return 0;
}
3.查找元素
给定一个有 n 个元素按照升序排列的整数数组 a1,⋅⋅⋅,an,和一个目标值 target。找出给定目标值在数组中的开始位置(第一个),结束位置(最后一个)以及与目标值相同的元素个数。
如果数组中不存在目标值 target,输出 -1 -1 0。
输入共 2 行:
第 1 行,两个正整数 n,target;
第 2 行,n 个空格隔开的正整数a1,a2,⋅⋅⋅,an。
输出共 1 行:
两个空格隔开的数据,给定目标值在数组中的开始位置和结束位置;
如果不存在,输出 -1 -1 0。
1≤n≤105;−109≤target,ai≤109。
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main()
{
int n,t;
cin >> n >> t;
for(int i=1;i<=n;i++) cin >> a[i];
int p1=lower_bound(a+1,a+n+1,t)-a;
int p2=upper_bound(a+1,a+n+1,t)-a;
if(p1!=p2)cout << p1 << " " << p2-1 << " " << p2-p1;
else cout << "-1 -1 0";
return 0;
}
这是我找到的关于二分查找的相关题目,希望能帮到你~~~
点个关注吧!!!
标签:二分,数字,109,int,bound,整数,a1,查找,c++ From: https://blog.csdn.net/2301_80279915/article/details/139545716