基础算法第一期：二分模板（数组+STL）

前言

二分是算法中十分重要的算法，因此应该记熟它的模板并且深刻的理解。初次制作希望大家多一份理解，可能制作的并不能让您满意，我会慢慢加油的，谢谢大家

一、二分是什么？

（1）到底什么是二分呢？简单来说二分就是在有序序列中，通过不断的二分，进而不断地缩小范围去寻找满足我们条件的解。这只是对二分一个狭义上的理解，广义二分其实是如果有一个临界值使得临界值一边的数据满足一种性质，另一边满足另一种性质，即使不是有序的但也可以利用二分去寻找这个临界值。接下来我将为大家讲解二分的模板以及如何理解

二、二分的模板及理解

1.正常版本

先给出模板，尽量理解背下来；接下来给出例题

int SL(int l,int r,int x)//从左边开始二分，返回的是x从左边第一次出现的位置
{
	while(l<r)//直到l==r时结束循环
{
		int mid=l+r>>1;//相当于除以2
		if(a[mid]>=x)r=mid;//说明要找的数小于等于中间值，应让右端点r=mid缩短范围，直接等于mid是因为可以取到等号
		else 
		l=mid+1;//说明要找的数较大,大于中间值，+1是因为x一定在mid+1到r之间
	}
	return l;
}
int SR(int l,int r,int x)//从右边二分找到其位置，返回的是x从右边第一次出现的位置
{
	while(l<r)//直到l==r时结束循环
{
		int mid=l+r+1>>1;//相当于除以2
		if(a[mid]<=x)l=mid;//说明要找的数大于等于中间值，应让左端点r=mid缩短范围直接等于mid是因为可以取到等号
		else r=mid-1;//说明要找的数较小，小于中间值，-1是因为一定在l到mid-1之间
	}
	return r;
}

#include<iostream>
using namespace std;
#include<vector>

const int N=1e5+10;
int n,q;
int a[N];

int SL(int l,int r,int x)//从左边开始二分
{
	while(l<r){
		int mid=l+r>>1;
		if(a[mid]>=x)r=mid;
		else 
		l=mid+1;
	}
	return l;
}
int SR(int l,int r,int x)//从右边二分找到其位置
{
	while(l<r){
		int mid=l+r+1>>1;
		if(a[mid]<=x)l=mid;
		else r=mid-1;
	}
	return r;
}
int main()
{
   cin>>n>>q;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	while(q--){
		int k;
		cin>>k;
	    int l=SL(0,n-1,k);
		if(a[l]!=k)cout<<"-1 -1"<<endl;
		else {
			cout<<l<<" ";
			cout<<SR(0,n-1,k)<<endl;
		}
	}
	return 0;
}

2.STL版本

先给出模板，再给出例题

inline void solve(int k,vector<int>&v)
{
	int l=lower_bound(v.begin(),v.end(),k)-v.begin();//STL专属函数
	int r=upper_bound(v.begin(),v.end(),k)-v.begin();//STL专属函数
	if(v[l]==k)cout<<l<<" ";
	else cout<<"-1 ";
	if(v[r-1]==k)cout<<r-1<<endl;
	else cout<<"-1"<<endl;
}

#include<iostream>
#include<vector>
using namespace std;
#include<algorithm>
vector<int>v;
int n,q,tmp;

inline void solve(int k,vector<int>&v)
{
	int l=lower_bound(v.begin(),v.end(),k)-v.begin();//从左边查找
	int r=upper_bound(v.begin(),v.end(),k)-v.begin();//从右边查找
	if(v[l]==k)cout<<l<<" ";
	else cout<<"-1 ";
	if(v[r-1]==k)cout<<r-1<<endl;
	else cout<<"-1"<<endl;
}

int main()
{
	cin>>n>>q;
	for(int i=0;i<n;i++){
		cin>>tmp;
		v.push_back(tmp);
	}
	while(q--){
		int k;
		cin>>k;
		solve(k,v);
	}
	return 0;
}

总结

上面就是我对二分这一块的理解，希望能够帮助到大家，谢谢大家，如果有不懂的地方请在下方留言，我看到了一定会及时回复的，感谢大家的观看