AcWing 789. 数的范围
原题链接
简单
作者:
种花家的老六
,
2022-09-25 22:56:37
,
所有人可见
,
阅读 331
二分之整数范围
在正式讲解之前,我们要知道二分是干啥用的
二分,其实就是一种查找算法,一般顺序查找的时间复杂度是o(n),而二分是提升时间复杂度的,可以将o(n)提升到o(logn)级别。一般二分查找分为两类:整数二分和实数二分。整数二分非常容易错,建议多研究。实数二分比较简单,一般大家琢磨琢磨就会了。
这题就是一个整数二分。
首先,我们知道,二分有两个模版:
int search_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int search_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid + 1;
}
return l;
}
我们要根据不同的题目调用不同的模版
那么,此题需要用什么模版呢?
仔细研究发现,这题要用第一个模版。
那么,把模版套入代码中就行了。
代码如下:
#include <iostream>
using namespace std;
const int maxn = 100005;
int n, q, x, a[maxn];
int main() {
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
while (q--) {
scanf("%d", &x);
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (a[mid] < x) l = mid + 1;
else r = mid;
}
if (a[l] != x) {
printf("-1 -1\n");
continue;
}
int l1 = l, r1 = n;
while (l1 + 1 < r1) {
int mid = l1 + r1 >> 1;
if (a[mid] <= x) l1 = mid;
else r1 = mid;
}
printf("%d %d\n", l, l1);
}
return 0;
}