算法基础算法

单调性与二分

字数统计: 1.5k字   |   阅读时长: 5分
,

摘要: 本文系统梳理了二分的算法要点。并汇总了 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