title: 0x04 二分
date: 2019-02-07 18:34:50
categories: 算法竞赛进阶指南
tags: 二分
mathjax: true
更好的阅读体验
整数域二分
二分模板一共有两个,分别适用于不同情况。
算法思路:假设目标值在闭区间[l, r]中, 每次将区间长度缩小一半,当l = r时,我们就找到了目标值。
版本1
当区间[l, r]的更新操作是r = mid; l = mid + 1;时,计算mid时不需要加1。
C++ 代码模板:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
解读
我们要在下面一串数中用上面的二分查找代码查找 11
第一次查询,(l+r)/2=4,查到 8 ,是小于 11 的,于是更新,l=4+1=5
第二次查询,(l+r)/2=6 ,查到12 ,是大于11的,于是更新,r=mid=6
第三次查询,(l+r)/2=5 ,查到10,是小于11的,于是更新,l=5+1=6
最终得到结果为12 。12是我们查找到这一串数中,大于等于11(查找数)中最小值。
我们可以得到一个结论:以上二分模板用来解,最大值最小问题。
版本2
当区间[l, r]的更新操作是r = mid - 1; l = mid;时,计算mid时需要加1。
C++ 代码模板:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
解读
我们要在下面一串数中用上面的二分查找代码查找 11
第一次查询,(l+r+1)/2=4,查到 8 ,是小于 11 的,于是更新,l=4
第二次查询,(l+r+1)/2=6,查到 12 ,是大于 11 的,于是更新,r=6−1=5
第三次查询,(l+r+1)/2=5,查到 10 ,是小于 11 的,于是更新,l=5
最终得到结果为10 。10是我们查找到这一串数中,小于等于11(查找数)中最大值。
我们可以得到一个结论:以上二分模板用来解,最小值最大问题。
二分答案
二分答案与二分查找类似,即对有着单调性的答案进行二分,大多数情况下用于求解满足某种条件下的最大(小)值。
答案单调性
答案的单调性大多数情况下可以转化为一个函数,其单调性证明多种多样,如下:
-
移动石头的个数越多,答案越大(NOIP2015跳石头)。
-
前i天的条件一定比前 i + 1 天条件更容易(NOIP2012借教室)。
-
满足更少分配要求比满足更多的要求更容易(NOIP2010关押罪犯)。
-
满足更大最大值比满足更小最大值的要求更容易(NOIP2015运输计划)。
-
时间越长,越容易满足条件(NOIP2012疫情控制)。
可以解决的问题
把求最优解的问题,转化为给定一个值 mid ,判定是否存在一个方案,达到 mid 的的问题。(二分答案转化为判定)。
- 求最大的最小值(NOIP2015跳石头)。
- 求最小的最大值(NOIP2010关押罪犯)。
- 求满足条件下的最小(大)值。
- 求最靠近一个值的值。
- 求最小的能满足条件的代价。
一个小例子
有 N 本书排成一行,已知第 i 本书的厚度是 Ai 。
把他们分成连续的 M 组,T 表示厚度之和最大的一组的厚度,使 T 最小。
问的是最大值最小,很明显是一道二分题,题目让求 T 值,我们可以直接来二分查找 T 的值,在整数数轴上,肯定存在值,使得 T 成立。呢么对应着使 T 成立的这段数轴上,肯定也存在一个值,使得 T 最小。
因此,可得,本题的做法就是,在整数数轴上二分查找一个 T 值。
这道题也没有测试数据,只是书上的一个举例,我就不打打码了。
参考资料
- Cosmos二分答案模板及二分答案问题讲解
- yxc二分查找算法模板
- 《算法竞赛进阶指南》 lyd
谢大佬!!!!!解决了困扰我一年的问题!
你好,想问下闭区间l和r是几?谢谢
int bsearch_2(int l, int r) { while (l < =r) { int mid = (l+r)>>1; if (check(mid)) l = mid+1; else r = mid - 1; } return l; }
请问下,这个也可以吧?谢谢
有错误,或者不懂的可以在评论区提出。
师兄,我的理解是这样的, 所谓整数二分无非就两种区间划分情况。
第一种:[l , mid] [mid+1, r]
第二种:[l , mid-1] [mid , r]
显然我们会思考,我们什么时候该用第一种,什么时候用第二种呢?
答:第一种情况 Min(>=x)
第二种情况 Max(<=x)
注:这里的>=x只是我们定义的check( )
我们知道该怎么用?但是我不太理解原理 求解