分治方法自动查找！
原题链接：455.lower and upper bound
2024-05-17 22:08:32
发布于：广东
26阅读
0回复
0点赞
#include <iostream>
#include <cstdio>
using namespace std;
int a[1000005];
int x;
int check1(int left, int right){//节省了很多代码
if(a[left] == x) return left;
if(a[left] > x || a[right] < x) return 0x3f3f3f3f;
return 0;
}int check2(int left, int right){
if(a[right] == x) return right;
if(a[left] > x || a[right] < x) return -1;
return 0;
}int check3(int left, int right){
if(a[left] > x) return left;
if(a[right] <= x) return 0x3f3f3f3f;
return 0;
}
int find(int left, int right, int check(int, int), bool is_up = 0){//这里只需要填check函数，是否要最大值就行了
int cxk = check(left, right);
if(cxk) return cxk;
if(left == right) return left;
int mid = (left + right) / 2;
if(is_up) return max(find(left, mid, check, 1), find(mid + 1, right, check, 1));
return min(find(left, mid, check), find(mid + 1, right, check));
}
int main(){
int n, m;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", a + i);
}scanf("%d", &m);
while(m--){
scanf("%d", &x);
int f1 = find(1, n, check1), f2 = find(1, n, check2, 1), f3 = find(1, n, check3);
printf("%d %d %d\n", (f1 == 0x3f3f3f3f ? -1 : f1), (f2 == 0x3f3f3f3f ? -1 : f2), (f3 == 0x3f3f3f3f ? -1 : f3));
}
return 0;
}
单次查找时间复杂度：
有帮助，赞一个