二分原理

作者:baihacker
来源:

二分原理:
设f是定义在[a, b]上的bool函数,且满足性质若f(i) = true则f(i+1) = true.
那么算法:
int l = a, r = b;
while (l <= r)
{
int mid = (l + r)/2;
if (f(mid)) r = mid - 1;
else l = mid + 1;
}
结束时一定有 l = r + 1;
那么有
l = b + 1或者l是最小的使得f的值为true的数.
同时
r = a - 1或者r是最大的使得f的值为false的数.
如果我们定义f(b+1) = true;
那么可以描述为
l是最小的使得f的值为true的数.
r是最大的使得f的值为false的数.

在有序的序列x1,x2,x3,...,xn找到i,使得xi >= value
根据上面的原理:
a = 1, b = 1;
f(i) = xi >= value;

这就是stl中的lower_bound,类似地可以得到upper_bound.
总之,二分原理可以求出满足单调性的函数的第一个满足某条件的值.

应用1:
给定含有n个整数的序列,可以把这个序列分为m个子序列.
对于每个子序列,定义这个序列上的数的和为这个序列的权重.
所有子序列的权重中最大的称为这个划分的权重.
最小的划分权重是多大?

直接解决这个问题不好解决.
反过来思考,给定权重x,最少可以划为多少份,这个问题可以用贪心算法解决.
定义f(x) = 在权重x下最少的划分份数 <= m.
显然x太小的话,这个函数为假false,x够大的话,这个函数的值为true.
找到第一个最少划分份数 <= m的x,显然有:
如果取x-1,那么要至少分为大于m部分,不合要求.
如果对于x的最少划分刚好是m,显然,这是最小权.
如果对于x的最少划分小于m,留给读者自己思考.

可以看出,利用二分原理可以把复杂的问题,转换为判定性问题.

应用2:
|v0 - x| + |v1 - x| + ... + |vN-1 - x| <= M.
给定v0, v1,...,vN-1,和M,求使得这个等满足的x的个数.(都考虑整数)
解的可能的范围是
[max - M, min + M]
当vi取值大,M也大的时候,显然不能直接求解.

很显然,如果存在解,肯定是连续的一段,只需要找出这一段的最小值和最大值.
就可以知道有多少个解了.
利用二分原理,可以自然地想到在[max - M, min + M]上二分出最小,最大值.
以最小值为例f(x) = F(x) <= M,找到使f(x)为真的第一个数.(F为|v0 - x| + |v1 - x| + ... + |vN-1 - x|)
对应的最大值就是f(x) = F(x) <= M为真的最后一个数,注意二分原理,令g(x) = !f(x)
就是g(x)为假的最后一个数.(其实就是在二分过程中,把l,r交换一下,在结束以后取r而不是取l)
且慢,这里满足条件吗?
f(x)=true则f(x+1)=true吗?
显然不一定满足.

可以先求F的最小值点k,要么最小值点满足f(k)=true,要么解不存在.
这样就可以分别在[k-m, k], [k, k+m]上二分.

如何求最小值点,这个问题比较简单,留给读者自己思考.


应用3:
给定一定数量的钱,要配一台电脑,电脑由若干个部件组成.每个部件有不同的档次,
档次低的便宜但是得到的性能值小.又假定用统一的性能值衡量每个部件,性能值
最小值的部件为整体性能值.要求组装出性能值最大电脑.

应用4:
求出第k个素数.

扩展:
类似二分的,还有三分求凸(凹)函数极值.
有的二分写法是while (l < r)道理是一样的,结束的时候l = r,可以类似地给出二分原理,他们的本质是一样的.
直观地理解二分原理,要求第一个满足要求的值,就是在当前值满足要求的时候往更小的找,
否则就往更大的找.
要找出最后一个满足要求的,就是在当前值满足要求的时候往更大的找,否则往更小的找.

应用1:
http://cs.scu.edu.cn/soj/problem.action?id=3166
应用2:
http://cs.scu.edu.cn/soj/problem.action?id=3253
应用3:
http://cs.scu.edu.cn/soj/problem.action?id=3202
应用4: