789. 数的范围
题目链接
思路
数据较大，且找左右端点，利用二分
此题考察二分写法
具体详见代码注释
我觉得二分的整体思路是很好理解的，难的地方就在于写法上的细节，比如要不要+1，要不要等于
总结小规律：
找哪边，哪边就+1，另一边就=
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
int a[N];
int n;
int main()
{int q;cin >> n >> q;for (int i = 1; i <= n; i ++ ){cin >> a[i];}while (q -- ){int ll, rr;int l = 1, r = n;int x;cin >> x;while (l < r) //标准模板 {int mid = (l + r) / 2; //中间值 if (a[mid] < x) //因为要找左端点，所以左端点等于时就不能动了，所以只能写小于 {l = mid + 1; //小于的话，+1后就有可能等于，以后就不动了 }else if (a[mid] >= x) //让左端点不动，让右端点往左边靠，在左右范围里都，数都相等的情况下，比如l = 2, r = 3. a[l] = 2 , a[r] = 3， 要找左端点，(2 + 3) / 2，得到2＝x,r就与l相等了 {r = mid;}}//如果找到了数，就记录答案 if (a[l] == x) {ll = l;}else //没找到数就输出-1 {cout << "-1 -1" << endl;continue;}//找右端点 l = 1, r = n;while (l < r){//因为(2 + 3) / 2 = 2，如果要找3，就永远找不到，就+1，让它往右边取 int mid = (l + r + 1) / 2;//与上面相反，这里是左边往右边靠，右边确定后不动，左边一步步靠近 if (a[mid] <= x){l = mid;} //-1后很有可能正好是x，那么就不动了，如果不是，缩小点范围也没有影响 else if (a[mid] > x){r = mid - 1;}}
// //上面已经判过，如果有解，那么此处也一定有解 cout << ll - 1 << " " << l - 1 << endl;}return 0;}
小扩展
>>1 右移一位相当于除以二