题目链接
一些话
切入点
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
说明了此题是查数组里的元素位置，由此知道是要用二分，作为题目的切入点
流程
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
说明题目给定的数组有序，不用再排序
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）
要查k区间的起始与终止，说明要写两段二分，一段f[mid] >= x,一段f[mid] <= x;
如果数组中不存在该元素，则返回 -1 -1。
二分完还要再判断结果是否等于该元素，不等的话输出-1
套路
1.二分的写法判断：
①找x区间里的第一个位置：
㈠用f[mid] >= x，
f[mid]在x区间里时要让mid尽可能小，所以要移动右边界，对应r = mid
mid = l + r >> 1
㈡为什么不能用f[mid] <= x ?
前面说到，要让mid尽可能小，所以要移动右边界，如果用f[mid] <= x,只要开始移 动右边界，f[mid] 就永远小于 x，右边界会无限移动直到l < r的条件被打破。
②找x区间里的最后一个位置：
㈠用f[mid] <= x,
f[mid]在x区间里时要让mid尽可能大，所以要移动左边界，对应l = mid(此时mid要
写成l + r + 1 >> 1;
㈡为什么不能用f[mid] >= x?
同情况①,会出现左边界无限移动的情况
ac代码
// 6;57~7:06 ~ 46 accepted; // 7:57 - 8 : 03 // 8:06~8:10 // 找第一个x，>= x, // 最后一个x <= x // 第一个x左边一位 ， < x // 最后一个x右边一位， > x #include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int N = 1e5 + 10; int f[N]; int n; int main(){ cin >> n; int t; cin >> t; for(int i = 0;i < n;i++){ scanf("%d",&f[i]); } while(t--){ int x; scanf("%d",&x); int l = 0,r = n-1; while(l < r){ int mid = l + r >> 1; if(f[mid] >= x) r = mid; else l = mid + 1; } if(f[l] == x) cout << l << " "; else cout << -1 << " "; r = n -1; while(l < r){ int mid = l + r + 1 >> 1; if(f[mid] <= x) l = mid; else r = mid - 1; } if(f[l] == x) cout << l << endl; else cout << -1 << endl; } return 0; }
