二分函数细节

在打ACM竞赛题时，二分是一种很基础的方法，但是有些时候往往疏忽了一些细节，导致二分循环可能会卡死，或者有BUG存在。
所以在下面总结一下二分函数的细节使用方法：

二分的基本规则：

在a[mid]<key 的时候，变化 l（左端点）
在a[mid]>key 的时候，变化 r (右端点）

---

当然上述规则，只是在 数组升序的情况下才成立
如果mid 和 key时成负相关 的情况下，上面的规则要倒过来

例如:二分城市投票点的最大人数时，在人数一定下，由于投票点人数越多，那么需要的投票点就越少，每个投票点人数越少，需要的投票点就越多，这种情况就需要把基本规则倒过来。

在这种情况下，只需要把上面这个基本规则反过来，其他规则都和正常一样就行

所以要具体情况，具体分析。

普通的二分

（l<=r)型二分
特点，在l,r变化的时候需要遵循
mid+1 和 r= mid-1 的规则

并且，如果 当判断条件时 a[mid]<=key时，r为二分的答案, r=l-1;
同样，当判断条件为 a[mid]>=key时，l为二分的答案，l=r+1;

（在变化时，等号在哪个变量上判断，答案就是另一个变量）

l为答案时：

用处：输出key的正确位置，找不到时输出第一个比key大的数字的位置
并且当有重复key时，输出第一个key的位置！

#include<bits/stdc++.h>
using namespace std;
int a[11]; 
int main()
{
	for(int i=1;i<=10;i++)//2 4 6 8 10 
	{
		a[i]=i*2;
	}
	
	int k;
	cin>>k;
	
	int l=1,r=10;
	int mid;
	
	while(l<=r)
	{
		mid=(l+r)/2;
		
		cout<<l<<" "<<r<<" "<<mid<<endl;
		if(a[mid]>=k)
		{
			r=mid-1;
		}
		else 
		l=mid+1;
	}
	
	cout<<l;//能输出准确答案，或者输出第一个比自己大的数字的位置！ 
	return 0;
}

r为答案时

用处：输出key的位置，找不到时输出第一个比自己小的数字的位置
当有重复的key时，输出最后一个key的位置！

#include<bits/stdc++.h>
using namespace std;
int a[11]; 
int main()
{
	for(int i=1;i<=10;i++)
	{
		a[i]=i*2;
	}
	
	int k;
	cin>>k;
	
	int l=1,r=10;
	int mid;
	
	while(l<=r)
	{
		mid=(l+r)/2;
		
		cout<<l<<" "<<r<<" "<<mid<<endl;
		if(a[mid]>k)
		{
			r=mid-1;
		}
		else 
		l=mid+1;
	}
	
	cout<<r;//能输出正确答案，并且能输出第一个比自己小的数字的位置！
	return 0;
}

（l<r-1)型二分

在l,r变化的时候，需要遵循
l=mid 和 r=mid 的区别 。
投票点

#include<bits/stdc++.h>
using namespace std;
int n,m;
int t[5001];
int judge(int mid)
{
	int num=0;
	for(int i=1;i<=m;i++)
	{
		num+=t[i]/mid;
		if(t[i]%mid!=0)
		num++;
	}
	return  num;
}
int main()
{
	cin>>n>>m;
	int mmax=-1;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i];
		mmax=max(mmax,t[i]);
	}
	
	int l=0,r=mmax;
	while(l<r-1)
	{
	    int mid=(l+r)/2;

	    if(judge(mid)<=m)
	    {
	    	r=mid;
		}
		else 
		{
			l=mid;
		}
	}
	cout<<r;
	return 0; 
}

---

用 l<=r型改写

#include<bits/stdc++.h>
using namespace std;
int t[5001];
int n,m; 
int judge(int mid)
{
	int num=0;
	for(int i=1;i<=m;i++)
	{
		num+=t[i]/mid;
		if(t[i]%mid!=0)
		num++;
	}
	return num;
}
int main()
{
	cin>>n>>m;
	int mmax=-1;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i];
		mmax=max(mmax,t[i]);
	}
	
	int l=0,r=mmax;
	while(l<=r)
	{
	    int mid=(l+r)/2;
		if(judge(mid)<=m)
	    {
		  r=mid-1; 
	    }
		else
		l=mid+1;
	}
	cout<<l;
	return 0; 
}