题目描述
给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。
对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。
如果数组中不存在该元素,则返回“-1 -1”。
样例
6 3
1 2 2 3 3 4
3
4
5
本人解题思路
首先是两个整数模板
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
上述模板是求第一个大于等于x的数,若a[mid] >= x,则显然x在左半边一侧,缩小范围令r = mid;否则l = mid + 1。
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (a[mid] <= x) l = mid;
else r1 = mid - 1;
}
上述模板是求第一个小于等于x的数,若a[mid] <= x,则显然x在右半边一侧,缩小范围令l = mid;否则r = mid - 1。且同时要把mid多加一个一不然死循环。
if (q[l] != x)
用来判断不满足的条件的情况,即:没有x该数。
浮点数二分较简单,不用考虑边界的问题
double l = -10000, r = 10000;
while (r - l > 1e-8) {
double mid = (l + r) / 2;
if (mid * mid * mid >= x) r = mid;
else l = mid;
}
在一个范围中二分即可
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n, k;
int q[N];
int main () {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> q[i];
while (k--) {
int x;
cin >> x;
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (q[mid] >= x) r = mid;
else l = mid + 1;
}
if (q[l] != x) cout << "-1 -1" << endl;
else {
cout << l << ' ';
int l = 0, r = n - 10;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (q[mid] <= x) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}