注:今天的内容稍稍有点水,不喜勿喷
一、二分查找(Binary Search)
原理说明
二分查找基于有序集合的减治策略,通过每次将搜索范围减半实现O(log n)时间复杂度。算法核心是维护查找区间[l, r],通过中间值mid与目标值的比较决定搜索方向。
经典案例:有序数组查找
应用场景:
数据库索引、游戏分数排行榜、词典查询等有序数据检索。
二、二分答案(Binary Search on Answer)
原理说明
当问题满足<单调性>条件时,通过二分枚举可能的解,用验证函数判断解的有效性。适用于"求最大最小值"或"最小最大值"类问题。
典型案例:木材切割
应用场景:
资源分配最优解、工程设计参数优化等。
三、进阶技巧
STL应用:
lower_bound/upper_bound实现
浮点数二分:
设置精度终止条件
旋转数组查找:
变形二分应用
三分查找:
处理单峰函数问题(这个……小女子不才,补会……)
最后:
原创不易,多多支持,多蟹!!😃😃