AcWing 789. 数的范围 C++
原题链接
简单
作者:
张立斌
,
2019-10-25 12:14:00
,
所有人可见
,
阅读 659
C++代码
#include <iostream>
#include <vector>
using namespace std;
// 满足条件的第1个值,不取右
template <typename Check>
int binarySearch1(int *arr, int left, int right, Check check) {
while (left < right) {
int mid = left + ((right - left) >> 1);
if (check(arr[mid])) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// 不满足条件的最后1个值,不取左
template <typename Check>
int binarySearch2(int *arr, int left, int right, Check check) {
while (left < right) {
int mid = (static_cast<int64_t>(left) + right + 1) >> 1;
if (check(arr[mid])) {
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
int main(void) {
int n, q;
scanf("%d%d", &n, &q);
if (n <= 0 || q <= 0) {
puts("");
return 0;
}
vector<int> vec(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &vec[i]);
}
for (int i = 0; i < q; ++i) {
int target;
scanf("%d", &target);
int frontIndex = binarySearch1(&vec[0], 0, n - 1, [&](int a) { return a >= target; });
if (vec[frontIndex] != target) {
puts("-1 -1");
continue;
}
int backIndex = binarySearch2(&vec[0], 0, n - 1, [&](int a) { return a > target; });
printf("%d %d\n", frontIndex, backIndex);
}
return 0;
}