二分
二分
二分的本质不是单调性。有单调性的题目一定可以二分,可以二分的题目不一定必须有单调性。
1. 整数二分
1.1 主要思想
在一个区间内部,使用二分的方法得到答案。每次选择答案所在的区间进行二分,且每次都能保证区间内有答案。对于有解的问题,二分得到的是正确答案;对于无解的题目,二分得到的是答案应该存在的位置。
1.2 整数二分的实现过程
- 找一个中间值,即
mid = (l + r) / 2
- (假设判断的是红色的性质)每次判断一下中间值是否满足性质,即
if(check(mid))
- 情况一:
true
- 说明
mid
满足该性质,因此ans
所在区间为[mid, r]
- 更新方式:
l = mid
- 说明
- 情况二:
false
- 说明
mid
不满足该性质,因此ans
所在区间为[l, mid - 1]
- 更新方式:
r = mid - 1
- 说明
- 情况一:
- (假设判断的是绿色的性质)每次判断一下中间值是否满足性质,即
if(check(mid))
- 情况一:
true
- 说明
mid
满足该性质,因此ans
所在区间为[l, mid]
- 更新方式:
r = mid
- 说明
- 情况二:
false
- 说明
mid
不满足该性质,因此ans
所在区间为[mid + 1, r]
- 更新方式:
l = mid + 1
- 说明
- 情况一:
中间值“是否+1”的问题
如果
mid = (l + r) / 2
,当l = r - 1
时,求得mid
的值为l
,倘若此时check()
正好取得true
,则会执行l = mid
,即l
更新后的值还是l
,就会陷入死循环状态。
1.3 模板
1 |
|
2. 浮点数二分
2.1 浮点数二分的实现过程
由于浮点数除法的结果仍然是浮点数,是保留精度的,其与整数除法的整除存在一定的差异。因此,浮点数二分不用考虑边界问题,其能够准确的把两个区间分为两部分。
2.2 模板
1 |
|
经验:如果题目要求保留4位小数,则
r-l
应该小于1e-6
;如果题目要求保留5位小数,则r-l
应该小于1e-7
;如果题目要求保留6位小数,则r-l
应该小于1e-8
。