AcWing 789. 数的范围
原题链接
简单
作者:
涛_04
,
2024-02-12 16:01:21
,
所有人可见
,
阅读 37
样例
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> q[i];
}
while (m--)
{
int x;
cin >> x;
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r >> 1;
if (q[mid] >= x)//这个判断条件,尽量多给等价情况
r = mid;//找左边界,r会一直往左走,直到到达左边最后一个满足的情况
else
l = mid + 1;
}
if (q[l] != x)
cout << "-1 -1" << endl;
else
{
cout << l << " ";
l = 0;
r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] <= x)
l = mid;//找右边界,l会一直往右走,
//直到到达右边最后一个满足的情况
else
r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}