二分算法
2022/8/7 1:22:56
本文主要是介绍二分算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二分的本质不是单调性。
(有单调性一定可以二分,但是二分可以做的题,不一定需要满足单调性。)
二分的本质是二段性
就是有一个分界点,分界点左边都是状态x,分界点右边都是状态y。
通过二分就可以找到红色区域的右边界值或者绿色区域的左边界值
当想找不满足性质的边界值(红色区域的右边界值)
即:将区间[l, r]划分成[l, mid]和[mid + 1, r]。
- 找中间值 \(mid =\frac{l+r}{2}\)
- if(check(mid))等于true或者是false
check(m)是检查m是在满足红颜色区间的性质(检查是不是在红色区间)
-
- 如果是true 正确区间:\([l,mid]\) ==> \(r=mid\)
-
- 如果是false 正确区间:\([mid+1,r]\) ==> \(l=mid+1\)
当想找满足性质的边界值(绿色区域的左边界值)
即:将区间[l, r]划分成[l, mid - 1]和[mid, r]。
-
找中间值 \(mid =\frac{l+r+1}{2}\)
计算mid时需要加1 -
if(check(mid))等于true或者是false
check(m)是检查m是在满足绿颜色区间的性质(检查是不是在绿色区间)
-
- 如果是true 正确区间:\([mid,r]\) ==> \(l=mid\)
-
- 如果是false 正确区间:\([l,mid-1]\) ==> \(r=mid-1\)
这篇关于二分算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行