[转帖]二分原理_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 1987 | 回复: 0   主题: [转帖]二分原理        下一篇 
linjun
注册用户
等级:中校
经验:2221
发帖:176
精华:2
注册:2013-1-6
状态:离线
发送短消息息给linjun 加好友    发送短消息息给linjun 发消息
发表于: IP:您无权察看 2013-1-10 14:13:07 | [全部帖] [楼主帖] 楼主

二分原理:
设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,可以类似地给出二分原理,他们的本质是一样的.
直观地理解二分原理,要求第一个满足要求的值,就是在当前值满足要求的时候往更小的找,
否则就往更大的找.
要找出最后一个满足要求的,就是在当前值满足要求的时候往更大的找,否则往更小的找.




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论