直接用模板,遇到的问题是 ,所选值在最大最小区间内,但是没有这个数值,
解决办法两种:
办法一: 当值在区间内,查找了左右边界之后,判断左边界是否小于等于右边界
#include <iostream>
using namespace std;
int sL(int arr[], int num, int l, int r){
while(l < r){
int mid = (l + r) >> 1;
if(arr[mid] >= num){
r = mid;
}else {
l = mid + 1;
}
}
return l;
}
int sR(int arr[], int num, int l, int r){
while( l < r){
int mid = (l + r + 1) >> 1;
if(arr[mid] <= num){
l = mid;
}else{
r = mid - 1;
}
}
return l;
}
int main(){
int n, q;
int arr[100010];
int num;
cin >> n >> q;
for(int i = 0; i < n; i ++){
cin >> arr[i];
}
for(int i = 0; i < q; i ++){
cin >> num;
if(num > arr[n - 1] || num < arr[0]){
//值不在区间范围内
cout << -1 << " " << -1 << endl;
} else {
int ll = sL(arr, num, 0, n -1);
int lr = sR(arr, num, 0, n - 1);
if(ll <= lr){
cout << ll << " " << lr << endl;
} else {
//右边界大于左边界
cout << -1 << " " << -1 << endl;
}
}
}
return 0;
}
办法二: 左界限和右界限 不相等说明数值存在, 相等时,判断一下 对应下标值是否为num
(只显示修改部分代码):
int main(){
...
for(int i = 0; i < q; i ++){
cin >> num;
int ll = sL(arr, num, 0, n -1);
int lr = sR(arr, num, 0, n - 1);
if(ll < lr || (ll == lr && arr[ll] == num)){
//ll 和lr 不相等说明数值存在, ll 和 lr相等,可能不存在,判断一下下标值是否为num
cout << ll << " " << lr << endl;
} else {
cout << -1 << " " << -1 << endl;
}
}
...
}