排序、二分与分治
学完这一节，你应该能够
利用有序性和问题规模缩减，把线性或平方搜索降到更低复杂度。
前置知识
- 算法基础与问题建模
- 基础数据结构
解题框架
- 排序与选择
- 二分查找
- 二分答案
- 分治与二分综合
母题路线
| 层级 | 解题框架 | 题目 | 站内题解 |
|---|---|---|---|
| 必学 | 排序与选择 | AcWing 785. 快速排序 | 阅读题解 |
| 必学 | 排序与选择 | AcWing 787. 归并排序 | 阅读题解 |
| 必学 | 排序与选择 | AcWing 788. 逆序对的数量 | 阅读题解 |
| 必学 | 排序与选择 | AcWing 786. 第k个数 | 阅读题解 |
| 必学 | 二分查找 | LeetCode 704. 二分查找 | 阅读题解 |
| 必学 | 二分查找 | LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 | 阅读题解 |
| 必学 | 二分查找 | LeetCode 35. 搜索插入位置 | 阅读题解 |
| 必学 | 二分查找 | LeetCode 33. 搜索旋转排序数组 | 阅读题解 |
| 必学 | 二分查找 | LeetCode 153. 寻找旋转排序数组中的最小值 | 阅读题解 |
| 必学 | 二分查找 | LeetCode 74. 搜索二维矩阵 | 阅读题解 |
| 必学 | 二分查找 | LeetCode 162. 寻找峰值 | 阅读题解 |
| 必学 | 二分答案 | LeetCode 875. 爱吃香蕉的珂珂 | 阅读题解 |
| 必学 | 二分答案 | LeetCode 1011. 在 D 天内送达包裹的能力 | 阅读题解 |
| 拓展 | 分治与二分综合 | LeetCode 4. 寻找两个正序数组的中位数 | 阅读题解 |
| 拓展 | 分治与二分综合 | LeetCode 378. 有序矩阵中第 K 小的元素 | 阅读题解 |
| 拓展 | 分治与二分综合 | LeetCode 287. 寻找重复数 | 阅读题解 |
| 拓展 | 分治与二分综合 | LeetCode 410. 分割数组的最大值 | 阅读题解 |
下一章： 数组与矩阵解题框架