题目链接
思路
数据较大,且找左右端点,利用二分
此题考察二分写法
具体详见代码注释
我觉得二分的整体思路是很好理解的,难的地方就在于写法上的细节,比如要不要+1,要不要等于
总结小规律:
找哪边,哪边就+1,另一边就=
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
int a[N];
int n;
int main()
{
int q;
cin >> n >> q;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
}
while (q -- )
{
int ll, rr;
int l = 1, r = n;
int x;
cin >> x;
while (l < r) //标准模板
{
int mid = (l + r) / 2; //中间值
if (a[mid] < x) //因为要找左端点,所以左端点等于时就不能动了,所以只能写小于
{
l = mid + 1; //小于的话,+1后就有可能等于,以后就不动了
}
else if (a[mid] >= x) //让左端点不动,让右端点往左边靠,在左右范围里都,数都相等的情况下,比如l = 2, r = 3. a[l] = 2 , a[r] = 3, 要找左端点,(2 + 3) / 2,得到2=x,r就与l相等了
{
r = mid;
}
}
//如果找到了数,就记录答案
if (a[l] == x)
{
ll = l;
}
else //没找到数就输出-1
{
cout << "-1 -1" << endl;
continue;
}
//找右端点
l = 1, r = n;
while (l < r)
{
//因为(2 + 3) / 2 = 2,如果要找3,就永远找不到,就+1,让它往右边取
int mid = (l + r + 1) / 2;
//与上面相反,这里是左边往右边靠,右边确定后不动,左边一步步靠近
if (a[mid] <= x)
{
l = mid;
} //-1后很有可能正好是x,那么就不动了,如果不是,缩小点范围也没有影响
else if (a[mid] > x)
{
r = mid - 1;
}
}
// //上面已经判过,如果有解,那么此处也一定有解
cout << ll - 1 << " " << l - 1 << endl;
}
return 0;
}
小扩展
>>1
右移一位相当于除以二