AcWing 789. 数的范围 (代码模板相对好记)
原题链接
简单
作者:
陈叔健爱学习
,
2022-03-31 21:40:59
,
所有人可见
,
阅读 149
模板
//在右半段寻找左边界(即寻找符合性质的第一个点)
int SL(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; //反
else l = mid + 1; //同
}
return l;
}
//在左半段寻找右边界(即寻找不符合性质的最后一个点)
int SR(int l, int r) //查找右边界 + 1
{
while (l < r)
{
int mid = l + r + 1 >> 1; //+1防止死循环
if (check(mid)) l = mid;//反
else r = mid - 1;//同
}
return r;
}
C++ 代码
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int SL(int l,int r,int x) {
while (l < r) {
int mid = l + r >> 1;
if(q[mid] >= x) {
r = mid ;
}
else {
l = mid + 1;
}
}
return l;
}
int SR(int l,int r,int x) {
while (l < r) {
int mid = (l + r + 1) / 2;
if(q[mid]<= x) {
l = mid;
}
else {
r = mid - 1;
}
}
return r;
}
int main() { int n,m;
scanf ("%d%d",&n,&m);
for(int i=0;i<n;++i) scanf ("%d",&q[i]);
while ( m-- ) {
int x;
scanf ("%d",&x);
int l = SL(0, n - 1, x);
if (q[l]!=x) cout <<"-1 -1"<<endl; //l 或r 都行 因为 这个时候r=l
else {
cout << SL(0, n - 1, x) << ' ';
cout << SR(0, n - 1, x) << endl;
}
}
return 0;
}