单调性与二分

  |  

摘要: 本文系统梳理了二分的算法要点。并汇总了 leetcode 上的相关的题目。

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文总结了力扣上 2000 题以内的关于二分的 83 道题。将场景相同的放到了一起,场景上主要涉及区间二分、值域二分、实数二分和三分。其中区间二分和值域二分都是很大的话题,里面还可以再细分。

区间二分主要针对有序数组,按照场景可以分为有序数组、旋转有序数组、预处理的有序数组、动态维护的有序数组、山脉数组、有序矩阵;

值域二分在取中间的二分点后,要求一次在该点对应的解,这个过程需要配合用到其它算法,配合的算法主要涉及简单判断、遍历、贪心、DFS、双指针、滑动窗口、二分、数学、字符串哈希、动态规划、前缀和、线段树等等,

这些都是主流算法和数据结构,最好都要掌握,下面的思维导图已经按照分类整理好了。刷完这份题目列表,力扣上的二分的问题可以说刷爆了。

关于函数的单调性及其性质,参考文章 一元函数的单调性、凸性与单峰性。本文在单调性的基础上给出二分的代码模板与题目清单。


$1 二分模板

1
2
3
4
5
6
7
8
9
10
11
// 范围为 [L, R]
int left = L, right = R;
while(left < right)
{
int mid = (left + right + 1) / 2;
if(_check(mid))
left = mid;
else
right = mid - 1;
}
return left;
1
2
3
4
5
6
7
8
9
10
11
// 范围为 [L, R]
int left = L, right = R;
while(left < right)
{
int mid = (left + right) / 2;
if(_check(mid))
left = mid + 1;
else
right = mid;
}
return left;

如果答案的存在性不能保证,如果循环退出后 left/right 落在 [L, R] 的边界上,需要验证。

$2 区间二分

有序数组

旋转有序数组

山脉数组

有序矩阵

动态维护的有序数组

为了避免 $O(N)$ 插入或者 $O(N)$ 删除很可能需要平衡树

预处理的有序数组

1
mapping[key] := 持有 key 的下标或位置数组

$3 值域二分

二分 + 直接 $O(1)$ 查询大了还是小了

二分 + 遍历

二分 + 贪心

二分 + DFS

二分 + 双指针

二分 + 滑动窗口

二分 + 二分

二分 + 数学

二分 + 字符串哈希

二分 + 动态规划

二分 + 前缀和

二分 + 线段树


Share