二分相关模型

感悟

感觉难点主要在要想到是否能用二分去写

很多题目在看过讲解后才恍然大悟原来这也能二分

但自己看的话怎么都不觉得可以二分

这个东西emm可能是不熟练导致的

反正照这几道题看来

现在已经有点眉目了

对于一些有单调性的题目（结果一定满足某一边满足某一边不满足）

比如最大最小解啊什么的这种很明显看得出来了

（发现这些题目都是在问一些最大是多少最小是多少这类的）

有个灵感就是

尝试把这个答案当成已知的

把区间划分成两段答案不一定非得在左半边也可能在右半边

（在左边找的是最大在右边找的是最小）

然后去任取一个满足条件的mid

看它要满足什么条件才能是在这个答案区间里面即check函数怎么写

然后再根据mid在答案的左边还是右边

去进行范围缩小移动l、r指针

——把不太好做的找最优解的问题转变成判定性的问题一直套答案不是就再猜一个答案

可以直接用库函数lower_bound( ）代替手写二分

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

在从大到小的排序数组中，重载lower_bound()和upper_bound()

lower_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

// 升序数组中：

upper_bound(a.begin(), a.end(), x); // 查找第一个 > x的元素

lower_bound(a.begin(), a.end(), x); // 查找第一个 >= x的元素

// 降序数组中：

upper_bound(a.begin(), a.end(), x, greater()); // 查找第一个 < x的元素

lower_bound(a.begin(), a.end(), x, greater()); // 查找第一个 <= x的元素

比如在二分模板题可以写成：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=100010;
int nums[N];
int n,q;

int SL(int l,int r,int k){
	while(l<r){
		int m=l+r>>1;
		if(nums[m]>=k)
			r=m;
		else
			l=m+1;
	}
	return r;
}

int SR(int l,int r,int k){
	while(l<r){
		int m=l+r+1>>1;
		if(nums[m]<=k)
			l=m;
		else
			r=m-1;
	}
	return r;
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=0;i<n;i++)
        cin>>nums[i];

    while(q--){
       	int k; cin>>k;

		//int l=SL(0,n-1,k);;
        int l=lower_bound(nums,nums+n,k)-nums;

        if(nums[l]!=k)
            cout<<"-1 -1"<<endl;
        else{
            cout<<l<<" ";
            // int r=SR(0,n-1,k);
            int r= upper_bound(nums,nums+n,k)-nums-1;

            cout<<r<<endl;
        }
    }
    return 0;
}