AcWing 789. 数的范围
原题链接
简单
作者:
RwChen
,
2021-06-23 16:22:36
,
所有人可见
,
阅读 238
利用折半找左右端点
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 10;
int nums[maxn];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%d", &nums[i]);
for(int i = 0; i < m; i++)
{
int target;
scanf("%d", &target);
int left = 0;
int right = n - 1;
//分出左端点
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] >= target)
right = mid;
else
left = mid + 1;
}
if(nums[left] != target)
{
puts("-1 -1");
}
else
{
//从左端点开始找右端点
int s = left;
right = n - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] <= target)
left = mid + 1;
else
right = mid;
}
if(nums[left] != target)
left--;
printf("%d %d\n", s, left);
}
}
return 0;
}