二分法，是通过不断缩小解的可能存在的范围，从而求得问题的最优解的方法。经常有二分与其他算法结合的题目。
1.从有序数组查找某个值 -- 以STL中的lower_bound与upper_bound为例
lower_boud( begin, end, val ) 函数输入需要查找的有序数列前闭后开区间，查找数列中第一个>=val的位置。而upper_bound返回数列中第一个>val的位置。
如果不存在符合条件的值则返回end(可能会越界)。如果数列中存在val，则[ lower_boud , upper_bound)之间的位置均为val。
lower_boud与upper_bound的实现(与STL中稍有不同):
int lower_bound( int *a, int length, int val )
{
int lb = 0, ub = length - 1;
while( ub-lb>1 )
{
int mid = (lb + ub) / 2;
if( a[mid]>=val ) ub = mid;
else lb = mid;
}
return ub;
}
int upper_bound( int *a, int length, int val )
{
int lb = 0, ub = length - 1;
while( ub-lb>1 )
{
int mid = (lb + ub) / 2;
if( a[mid]>val ) ub = mid;
else lb = mid;
}
return ub;
}
可以这样理解：对于lower_bound，如果此时的 mid 满足 a[ mid ] >= val ，那么就将右端点变为mid，让区间向左端靠近，最后的mid为最左端且满足>=val的位置。
同理upper_bound：让区间向满足>val的位置靠近，一步步缩小区间长度。
2.判断一个解是否可行
Cable master (POJ No.1064 ) 参见《挑战程序设计竞赛》p140
有N条绳子，它们的长度分别是Li。如果我们从它们中切割出K条长度相同的绳子的话，每条绳子最长有多长？答案保留到小数点两位数。
与上面搜索的思路类似，我们用C(x)：每条绳子为x满足切割出K条的条件。每次判断条件是否成立，如果成立则用二分的方式将区间向右端移动(lb = mid)。
那么现在的问题是如何高效实现C(x)：对于长度为Li的绳子最多能切割floor(Li / x)个绳子，那么所有能切割绳子个数的总和>=K即满足条件。
#include<cstdio>
#include<cmath>
const int Max_N = 10000;
const int INF = 1e8;
int N,K;
double L[Max_N];
bool C( double x );
void solve();
int main()
{
scanf("%d%d",&N,&K);
for( int i=0; i<N; i++ ) scanf("%lf",&L[i]);
solve();
return 0;
}
bool C( double x )
{//判断是否满足条件
int cnt = 0;
for( int i=0; i<N; i++ )
{
cnt += (int)(L[i] / x);
}
return cnt>=K;
}
void solve()
{
//初始化解的范围
double lb = 0, ub = INF;
//重复循环,直到解的范围足够小
for( int i=0; i<100; i++ )
{
double mid = (lb + ub) / 2;
// printf("mid = %.2lf\n",mid);
if( C(mid) ) lb = mid;//区间向右移动
else ub = mid;
}
printf("%.2lf\n",floor(lb*100)/100); //保留二位小数
}
二分搜索法结束的判定：在输出小数问题中，一般会指定允许的误差范围或是指定输出中小数点后面的位数。因此在使用二分搜索法时，有必要设置合理的结束条件
来满足精度的要求。在上面的程序中我们指定了程序的循环次数作为终止条件。1次循环可以把区间缩小一半，100次循环则可以达到1e-30的精度范围，基本上是没有
问题的。此外还可以把中制条件设为( ub - lb ) > EPS，指定区间的大小。在这种条件下，如果EPS取得太小，就有可能会因为浮点小数精度问题的原因陷入死循环，请千万小心。
3.最大化最小值
愤怒的牛 https://www.dotcpp.com/oj/problem2346.html
农夫 John 建造了一座很长的畜栏，它包括N(2≤N≤100,000)个隔间，这些小隔间依次编号为x1,...,xN(0≤xi≤1,000,000,000). 但是，John的C(2≤C≤N)头牛们并不喜欢这种布局，
而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢?
类似最大化最小值/最小化最大值的问题，通常可以用二分法就可以很好的解决。
我们令C( d )：可以安排牛的位置使得任意两头牛的位置都不小于d。
C(d)的判断可以用贪心法很好的解决：
对牛舍的位置排序
把第一头牛放入x0的牛舍
如果第 i 头牛放入 xi ，则第 i+1 头牛放入 xk - xj >= d 的最小的k中
之后思路与之前类似：二分判断，如果 d 符合条件则让区间向右端移动(l = mid)，否则向左移动。
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 1e8;
const int Max_N = 100000;
int N,M; //N个隔间 M头牛
int x[Max_N];
bool C( int d );
void solve();
int main()
{
scanf("%d%d",&N,&M);
for( int i=0; i<N; i++ ) scanf("%d",&x[i]);
solve();
return 0;
}
bool C( int d )
{
int last = 0; //当前牛位置x[last]
for( int i=1; i<M; i++ )
{
int crt = last + 1; //下一头符合条件的最左端位置
while( crt<N && x[crt]-x[last]<d )
{
crt++;
}
if( crt==N )
{//直到最后一个隔间都无法满足条件
return false;
}
last = crt; //更新last
}
return true;
}
void solve()
{
/*对隔间排序*/
sort(x,x+N);
/*初始化解的范围*/
int lb = 1, ub = INF;
/*二分求解*/
while( ub-lb>1 )
{
int mid = (lb + ub) / 2;
if( C(mid) ) lb = mid;
else ub = mid;
}
printf("%d\n",lb);
}
数列分段II https://www.dotcpp.com/oj/problem2348.html
对于给定的一个长度为N的正整数数列A[i]，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列4 2 4 5 1要分成3段
将其如下分段：
[4 2][4 5][1]
第一段和为6，第2段和为9，第3段和为1，和最大值为9。
将其如下分段：
[4][2 4][5 1]
第一段和为4，第2段和为6，第3段和为6，和最大值为6。
并且无论如何分段，最大值不会小于6。
所以可以得到要将数列4 2 4 5 1要分成3段，每段和的最大值最小为6。
最大化最小值，同样的二分思路，唯一不同的是C( d )的实现。
令C( d )：任意段的和不大于d。其实现仍然可以用贪心法：
last初值为0
找到使得下标从last-crt和不大于d的最大crt。
last = crt + 1
#include<cstdio>
const int INF = 1e8;
const int Max_N = 100000;
int N,M; //N个整数 M段
int x[Max_N];
bool C( int d );
void solve();
int main()
{
scanf("%d%d",&N,&M);
for( int i=0; i<N; i++ ) scanf("%d",&x[i]);
solve();
return 0;
}
bool C( int d )
{
int last = 0; //当前区间左端点
for( int i=0; i<M; i++ )
{
int sum = x[last];//区间和
if( sum>d ) return false;//单个数字就超过最大值
int crt = last + 1;
while( crt<N && sum+x[crt]<=d )
{
sum += x[crt];
crt++;
}
if( crt==N )
{//数字用完,说明可以分>=M段(比如d=INF则crt=N时i=0)
return true;
}
last = crt;
}
return false; //如果没用完数字则不符合条件
}
void solve()
{
/*初始化解的范围*/
int lb = 1, ub = INF;
/*二分求解*/
while( ub-lb>1 )
{
int mid = (lb + ub) / 2;
if( C(mid) ) ub = mid; //区间向左端移动
else lb = mid;
}
printf("%d\n",ub);
}
4.最大化平均值
有n个物品的重量和价值分别是 wi 和 vi 。从中选出 k 个物品使得单位重量的价值最大。
样例：输入 n = 3，k = 2，( w，v ) = { (2，2)，(5，3)，(2，1)} 输出0.75(选择0号和2号物品)
最开始想到的是贪心法求解：选取前 k 个单位重量价值最大的物品。但样例就是一个反例：按贪心策略应该选取0号和1号物品，但其单位重量价值并不是最大。
实际上这一题可以用二分法求解：
令C( x )：可以选取 k 个物品使得单位重量价值不小于x。那么只要求满足C( x )成立的最大x即可。
问题变为C( x )如何实现：假设我们选取物品的某个集合S，那么其单位重量价值为∑([i∈S])vi / ∑([i∈S])wi。
C( x ) : ∑( [ i ∈ S ] )vi / ∑( [ i ∈ S ] )wi >= x -->
∑( [ i ∈ S ] )vi >= x * ∑ ( [ i ∈ S ] )wi -->
∑( [ i ∈ S ] )( vi - x*wi ) >=0
因此，我们可以对 vi - x*wi 贪心选取：选择前 k 个最大的 vi - x * wi，判断和是否>=0。
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 1e8;
const int Max_N = 10000;
int n,k;
int w[Max_N], v[Max_N];
double res[Max_N]; //保存 vi - x*wi
bool C( double x );
void solve();
int main()
{
scanf("%d%d",&n,&k);
for( int i=0; i<n; i++ )
{
scanf("%d%d",&w[i],&v[i]);
}
solve();
return 0;
}
bool C( double x )
{
for( int i=0; i<n; i++ )
{
res[i] = v[i] - x*w[i];
}
sort(res,res+n);
/*计算res最大的k个数的和*/
double sum = 0;
for( int i=0; i<k; i++ )
{
sum += res[n-i-1];
}
return sum>=0;
}
void solve()
{
/*解的区间*/
double lb = 0, ub = INF;
for( int i=0; i<100; i++ )
{//用循环次数保证精度
double mid = (lb + ub) / 2;
if( C(mid) ) lb = mid;
else ub = mid;
}
printf("%.2lf\n",lb);
}