AcWing 789. 数的范围
原题链接
简单
作者:
Sou1Power
,
2022-04-20 19:52:37
,
所有人可见
,
阅读 160
二分查找,两个模板就可以解决所有整数二分的题目
C++ 代码
//因为是升序排列的数组,所以我们可以用二分查找
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for(int i = 0;i<n;i++) scanf("%d",&a[i]);
while(q--)
{
int k;
scanf("%d",&k);
int l = 0;
int r = n;
while(l<r) //该二分查找是查找k的初始位置
{
int mid = l + r >> 1; //因为下面是r = mid,所以不用+1
if(a[mid]>=k) //"性质"
{
r = mid; //a[mid]可能是目标答案,故是r=mid而不是mid-1.
}
else
{
l = mid + 1; //若上面是r = mid,else就肯定是l = mid + 1
}
}
if(a[l]!=k) //当l==r,退出循环。判断序列中是否有k这个数
{
cout<<"-1 -1"<<endl;
}
else //输入的数组里至少有一个数等于k
{
cout<<l<<' '; //此时l==r,输出r也是一样的
int l = 0; //一定要记得重新初始化l和r
int r = n-1;
while(l<r) //继续进行查找k的终止位置的二分查找
{
int mid = l + r +1 >> 1; //因为下面是l=mid,所以要加一
if(a[mid]<=k)
{
l = mid; //此时mid可能是答案,所以不是mid+1
}
else
{
r = mid - 1;
}
}
cout<<l<<endl;
}
}
return 0;
}