type
status
date
slug
summary
tags
category
icon
password
comment
二分
二分是一种从有序结果中寻找答案的快速的方法
如何写出正确的二分需要一定经验,可以在二分过程中,记录ans,也可以在判断答案可行性时,对边界值进行分析,只要能写正确,就是好的二分,因为想要写出正确的二分,对很多初学者来说并不容易
二分经验总结
下面介绍一种我认为比较优雅通用的写法:
总结:
- 第一点,首先满足答案一定在接下来的二分区间内,调节
(l,mid [+1,-1 )
这个二分区间即可
- 第二点,调节
mid
获取方式,在除以二之后,是否加减一会决定二分函数最后是否会收敛于ans
,因为除二的结果会向下取整,不熟悉的同学可以带入erfen(3,4)
这样的例子进行逻辑检验
- 目前来看,只要能够注意以上两点,就能写出正确的二分
- Author:E1ainay
- URL:https://e1ainay.top/article/alogrithmwiki/erfen
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts