算法
左闭右开的写法,第一次二分求>=target的第一个数,第二次二分求>target的第一个数。
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int nums[N];
void helper(int nums[], int l, int r, int target, int n) {
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= target) {
r = mid;
}
else {
l = mid + 1;
}
}
if (l == n || nums[l] != target){
cout << "-1 -1" << endl;
return;
}
cout << l << " ";
l = 0, r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > target) {
r = mid;
}
else {
l = mid + 1;
}
}
cout << l - 1 << endl;
}
int main() {
int n, q;
cin >> n >> q;
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
for (int i = 0; i < q; i++) {
int target;
cin >> target;
helper (nums, 0, n, target, n);
}
}