02.5 二分与排序
所属:全栈开发面试题库 / 02 数据结构与算法
覆盖范围
- 二分区间定义、lower/upper_bound、边界防死循环、mid 防溢出、不变量
- 旋转数组分段有序查找、找最小值、重复元素退化、局部峰谷
- 二分答案:可行单调、check 判定、最大/最小可行值、吃香蕉、分割数组、运包裹
- 二维有序矩阵搜索、第 K 小、二维峰值、单调函数求根、BST 查找
- 基础排序与稳定性:冒泡/选择/插入、复杂度对比、计数/桶/基数概念
- 快排与三路划分:Lomuto/Hoare、pivot 策略、快速选择、荷兰国旗
- 归并排序与逆序对:稳定归并、链表归并、逆序对批量计数、右侧更小元素
- 堆排序与工程排序:堆排、Top-K 堆、双堆中位数、外部排序多路归并、选型
子主题
| 编号 | 主题 | 覆盖范围 |
|---|---|---|
| 02.5.1 | 二分查找 | 4 个子主题 80 题:模板与边界、旋转数组与部分有序、二分答案、二维矩阵与非数组二分 |
| 02.5.2 | 排序算法与设计 | 4 个子主题 80 题:基础排序与稳定性、快排与三路划分、归并与逆序对、堆排序与工程排序 |
面试题索引
| 编号 | 题目 | 难度 | 频率 | 所在页面 |
|---|---|---|---|---|
| 02.5.1.1-002 | 基本二分查找(LC 704) | 简单 | ★★★★★ | 二分模板与边界 |
| 02.5.1.1-004 | lower_bound 第一个 ≥ target | 中等 | ★★★★★ | 二分模板与边界 |
| 02.5.1.1-010 | 搜索插入位置(LC 35) | 简单 | ★★★★☆ | 二分模板与边界 |
| 02.5.1.2-002 | 搜索旋转排序数组(LC 33) | 中等 | ★★★★★ | 旋转数组与部分有序 |
| 02.5.1.2-003 | 旋转数组含重复(LC 81) | 中等 | ★★★☆☆ | 旋转数组与部分有序 |
| 02.5.1.2-004 | 找旋转数组最小值(LC 153) | 中等 | ★★★★☆ | 旋转数组与部分有序 |
| 02.5.1.3-005 | 爱吃香蕉的珂珂(LC 875) | 中等 | ★★★★☆ | 二分答案 |
| 02.5.1.3-006 | 分割数组最大值(LC 410) | 困难 | ★★★★☆ | 二分答案 |
| 02.5.1.3-007 | 运送包裹(LC 1011) | 中等 | ★★★★☆ | 二分答案 |
| 02.5.1.4-002 | 搜索二维矩阵 I(LC 74) | 中等 | ★★★★☆ | 二维矩阵与非数组二分 |
| 02.5.1.4-003 | 搜索二维矩阵 II(LC 240) | 中等 | ★★★★☆ | 二维矩阵与非数组二分 |
| 02.5.1.4-007 | 有序矩阵第 K 小(LC 378) | 中等 | ★★★☆☆ | 二维矩阵与非数组二分 |
| 02.5.2.1-007 | 常见排序稳定性对比 | 基础 | ★★★★★ | 基础排序与稳定性 |
| 02.5.2.1-008 | 常见排序复杂度对比 | 基础 | ★★★★★ | 基础排序与稳定性 |
| 02.5.2.2-001 | 快速排序基本思想 | 中等 | ★★★★★ | 快排与三路划分 |
| 02.5.2.2-007 | 三路划分解决重复元素 | 中等 | ★★★★☆ | 快排与三路划分 |
| 02.5.2.2-010 | 快速选择第 K 大(LC 215) | 中等 | ★★★★★ | 快排与三路划分 |
| 02.5.2.2-014 | 荷兰国旗问题(LC 75) | 中等 | ★★★★☆ | 快排与三路划分 |
| 02.5.2.3-002 | 归并排序实现 | 中等 | ★★★★★ | 归并排序与逆序对 |
| 02.5.2.3-008 | 归并求逆序对 | 困难 | ★★★★☆ | 归并排序与逆序对 |
| 02.5.2.4-006 | 第 K 大元素堆法(LC 215) | 中等 | ★★★★★ | 堆排序与工程排序 |
| 02.5.2.4-008 | 外部排序概念与流程 | 高级 | ★★★☆☆ | 堆排序与工程排序 |
| 02.5.2.4-018 | 排序选型总结 | 基础 | ★★★★☆ | 堆排序与工程排序 |
当前状态
- 02.5.1 已完成 4 个子主题、80 题;02.5.2 已完成 4 个子主题、80 题,合计 160 题,全部为可学习型详解。
- 页面结构:知识域首页 + 子主题页 + 分册 TOC 三层登记。
- 代码以 Java 为主;复杂度标注平均/最坏/均摊口径,不确定版本行为标注待确认。