slug
recursive
type
Post
status
Published
category
8-AP CSA
date
Jan 4, 2026
summary
tags
concepts
password
icon
4.17 Recursive Searching and Sorting
课时：90 minutes
一、本课回顾与目标
在之前的学习中，你已经学过：
- Linear Search（线性搜索）
- Binary Search（二分搜索）
- Selection Sort（选择排序）
- Insertion Sort（插入排序）
这些算法都是用循环（iteration）实现的。
在本课中，你将学习：
- 递归版本的 Binary Search
- 递归排序算法：Merge Sort
你将看到：
👉 递归不仅可以处理数字，也可以遍历数组、ArrayList 和字符串
二、4.17.1 Recursive Binary Search
1. 回顾：Linear Search vs Binary Search
Linear Search
- 从头到尾逐个检查元素
- 不要求数组有序
- 时间复杂度：O(n)
Binary Search
- 从中间元素开始
- 每次排除一半数据
- 必须在有序数组或 ArrayList 上使用
- 时间复杂度：O(log n)
2. Binary Search 的递归思想
递归版 Binary Search 的核心思路是：
- 检查当前范围的 中间元素
- 如果找到目标，返回索引
- 如果目标更小，只搜索左半部分
- 如果目标更大，只搜索右半部分
- 如果搜索范围为空，说明目标不存在
3. 递归 Binary Search 的 Base Case（非常重要）
递归必须有终止条件（base case）。
在 Binary Search 中，有 两个 base case：
- 中间元素等于目标值
- 搜索范围已经无效（end < start）
如果没有第二个 base case，程序会无限递归，最终导致错误。
4. 递归 Binary Search（Java 示例）
5. 思考活动
问题 1
递归 Binary Search 的 base case 是什么？
问题 2
如果要搜索数组从索引
0 到 middle，递归调用应该怎么写？问题 3
如果删除
end < start 这个判断，会发生什么？👉 程序将无法停止递归，最终出错。
三、4.17.2 Merge Sort（归并排序）
代码解读
1. 为什么要学 Merge Sort？
之前学过的排序算法：
- Selection Sort
- Insertion Sort
它们的时间复杂度都是 O(n²)。
Merge Sort 更快，因为它像 Binary Search 一样：
- 每次把问题规模 减半
- 使用 Divide and Conquer（分治）思想
2. Merge Sort 的基本思想
Merge Sort 的过程分为三步：
- Divide
把数组拆成左右两半
- Conquer
递归排序左右两部分
- Merge
把两个有序数组合并成一个有序数组
3. Merge Sort 的关键特征（考试必认）
一个标准的 Merge Sort 通常包含：
- 3 个方法
mergeSortmergeSortHelper（递归）merge
- 使用一个辅助数组来合并数据
- 最终把结果复制回原数组
4. Merge Sort 的执行示例（Tracing）
Merge Sort 的执行示例（Tracing）
5. Merge Sort 的时间复杂度
- 无论数据是否有序
- Merge Sort 的执行时间 始终是 O(n log n)
6. 选择题练习
- 作者:NotionNext
- 链接:https://tangly1024.com/article/recursive
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章
