AcWing 789. 数的范围
原题链接
简单
作者:
qing123
,
2021-01-24 20:12:41
,
所有人可见
,
阅读 263
2分算法
#include<iostream>
using namespace std;
const int N=1e6+10;
int q[N],n;//存放数据和用户的输入
//前提 :输入数据升序排序
//寻找开始位置,目标值在数组中的左区间
/*
为什么是左区间 在分出的区间中mid=x是在左边界,
因为每次遇到相邻的数字的时候是向下取整
*/
int get_left(int x)
{
int l=0,r=n-1;
while(l<r)
{
//查找该数的左边界
int mid=l+r>>1; //向下取整
if(q[mid]>=x)r=mid;//要包含mid即左区间
else l=mid+1;
//printf("%d在区间[%d,%d]\n",x,l,r);
}
return l;
}
int get_right(int x)
{
int l=0,r=n-1;
//用l,r作为索引进查找目标的位置
while(l<r)
{
int mid=l+r+1>>1;//向右进行取整
if(q[mid]>x) r=mid-1 ;//目标解就在左边
else l=mid; //目标解在右边,包含mid
}
return r;
}
int main()
{
int m;
scanf("%d%d",&n,&m);//输入数组长度和讯问数据个数
for(int i=0;i<n;i++) scanf("%d",&q[i]);
int x;
for(int i=0;i<m;i++)
{
cin>>x;
int l=get_left(x),r=get_right(x);
if(x!=q[l])//没找到该数字
cout<<"-1 -1"<<endl;
else
cout<<l<<' '<<r<<endl;
}
return 0;
}