lower_bound、upper_bound模拟及解析

函数作用

lower_bound()返回二分查找第一个大于或等于x的数字的下标 stl的是返回指针
upper_bound()返回二分查找第一个大于x的数字下标，stl的是返回指针

stl中如果不存在则返回end（）也就是实际数组空间的后一个位置，这样就越界了，一定要判断下在访问指针指向数据，我写的模拟函数也一样，stl很多查找函数都是这样的。

易错点：

我手写的
lower_bound()函数while循环如果只执行if语句，
循环结束后：low = high+1;
else不执行 ：high = n -1；不变
所以 low = n；
那么如果数组大小是n
num[low]就会越界

如果lower函数只执行else语句也会造成
high = -1；从而越界

所以对返回的下标要判断会不会越界

同样对于upper_bound()函数也会这样

编写思路

思路
①判断循环结束条件
②判断left ,right是否要进行左移右移
③判断最后一次二分后x的位置（存在x)时

具体思路与逻辑注释在代码里了

// num 查找的数组，left 第一个数的下标，right 最后一个数的下标的后一位，x 要查询的数
int lower_bound(vector<ll> &num,int left ,int right ,ll x){
    --right;int middle = (left + right)>>1;while(left <= right){
         // ①left == right 时才能取到right 所以要‘=’//由①：②这样最后一次二分开始前一定是left == right == middle(这个条件可以推出下面)if(num[middle]<x)    //由①：对任何可能的数据都要使left > right（循环退出) 所以要left right 值都要偏移 left = middle+1;  //由②：(如果有x) 不断靠近区间最左x 最后一次二分后x的下标恰好为middle + 1else right = middle-1;//由②：(如果有x,求最左所以>=x都要左移) 最后一次二分后num[middle] == x；left = middle middle = (left + right)>>1;}return left ;//如果有X一定在left}

代码思想与上个相同

// num 查找的数组，left 第一个数的下标，right 最后一个数的下标的后一位，x 要查询的数
int upper_bound(vector<ll> &num,int left ,int right, ll x){
    //右开 求从左到右大于x的第一个数--right;//int left = 0,right = n - 1;//数组下标n*n不存数int middle = (left + right)>>1;while(left <= right){
    //最后一次二分开始前 left == right == middle if(num[middle]<=x)left = middle + 1;//右移 else right = middle-1;//左移 middle = (left + right)>>1;}return left;//如果有X一定在left
}

结构体lower_bound

struct point{
        //要把查询区间的左右值和修改修改的点的下标一起加入数组ll index,sum;// 一起离散化，这样就一定能找到查找的区间了point (){
    }    point(ll a, ll b):index(a), sum(b){
    }
};bool operator < (const point &x,const point & y) {
    //引用更快return x.index < y.index;
}int p = upper_bound(a.begin(),a.end(),point(x,0)) - a.begin();