题目描述
blablabla
样例
blablabla
算法1
脑袋里一定把过程想明白
C++ 代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
using namespace std;
const int N = 1e5;
int m;
int q[N];
int main()
{
int n;
cin >> n >> m;
for (int i = 0; i != n; i++)
{
cin >> q[i];
}
for (int i = 0; i != m; i++)
{
int x;
cin >> x;
int l = 0, r = n - 1;
int mid;
//二分查找左边界
while (l <= r)
{
mid = l + r >> 1;
if (q[mid] < x)l = mid + 1;
else r = mid - 1;
}
if (q[l] != x)cout << "-1 -1" << endl;
else//寻找右边界
{
int a = l;
l = mid;
r = n - 1;
while (l <= r)
{
mid = r + l + 1 >> 1;//注意左右边界的区别
if (q[mid] > x)r = mid-1;
else l = mid + 1;
}
cout << a << " " << r << endl;
}
}
}
1、注意平凡情况,本题目中即为l=r-1时,在循环内要么l=mid+1,要么mid=l+r+1>>1,否则会陷入死循环。我的代码中将递归条件改为了l<=r时,也能避免死循环
2、注意边界条件,check和对l、r的处理要匹配。>、>=一定要想清楚。