二分查找【含左边界查询 + 右边界查询】
789. 数的范围 - AcWing题库
二分查找看起来是很简单的一个算法，但是其中涉及到比较多的细节问题。
一不小心就死循环了……
使用条件
一般情况下，二分查找通常适用于一个有序的序列中（一般为升序）
算法解析
确定左右边界
首先我们需要确定 左边界left和右边界right
通常情况下
- left = 0
- right = n - 1（n为数组的长度）
这里需要注意的是，定义的left 和 right若后续有多个输入，最好定义在循环里面
执行循环
while(l < r){mid = l + r >> 1;if(q[mid] >= x) r = mid;else l = mid + 1;}if(q[l] != x) cout << "-1 -1" << endl;
使用while进行循环，循环条件是 left < right
如果出现left >= right那证明两边的数组都寻找完了，判断q[left]是否为想要查询的值x
问题一：为什么要判断
left而不是mid呢？因为这里我们讲的是二分中一种特殊情况，需要寻找的数在数组中
重复出现。所以如果采用
q[mid]则无法确定它是不是第一个等于x的下标
问题二：如何做到找到第一个为x下标的呢？
这里我们可以使用一个图进行表示
假设当前我们有下面这样的一个数组，需要寻找的数字为
2
开始时
left = 0，right = 6，其中mid = 3当前q[mid] = 2 >= 2，所以 右边界直接收缩至
Right = 3处
继续执行，left = 0，right = 3，所以mid = 1
此时，mid= 1 ，条件依然满足
right = 1
继续执行，left = 0 ，right = 1 ，所以mid = 0
此时
q[mid] < x，所以我们就找到了第一个等于x的数据
在判断存在需要寻找值后，继续寻找最右侧的值。
l = 0 , r = n - 1;while(l < r){mid = l + r + 1 >> 1;if(q[mid] <= x) l = mid;else r = mid - 1;}cout << l << endl;同样的原理，当我们判断<=时，就能找到第一个大于x的前一个值
代码模板
#include<iostream>using namespace std;const int N = 100008;
int n , m ;
int q[N];
int x;int main(){cin >> n >> m ;for(int i = 0 ; i < n ; i ++ ){cin >> q[i];}while(m --){cin >> x;int l = 0 , r = n - 1 ;int mid ;while(l < r){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 << " ";l = 0 , r = n - 1;while(l < r){mid = l + r + 1 >> 1;if(q[mid] <= x) l = mid;else r = mid - 1;}cout << l << endl;}}return 0;
}