slug
type
status
category
date
summary
tags
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）
一、Merge Sort 核心思想（一句话版）
分而治之（Divide & Conquer）把数组不断 一分为二，直到只剩 1 个元素（天然有序），再 两两合并（merge），在合并过程中完成排序。
二、示例数据（用于 Tracing）
我们用一个经典的小数组，方便完整追踪：
三、递归拆分过程（Divide 阶段）
📌 关键观察（讲给学生听）
- 当子数组长度为 1 时，递归停止
- 这就是 base case
四、合并过程（Merge 阶段，重点 Tracing）
1️⃣ 合并 [3] 和 [5]
2️⃣ 合并 [8] 和 [3, 5]
3️⃣ 合并 [7] 和 [4]
4️⃣ 合并 [2] 和 [4, 7]
5️⃣ 最终合并 [3, 5, 8] 和 [2, 4, 7]
五、完整 Java 代码（标准教学版）
六、课堂强调的 4 个考点（非常重要）
✅ 1. Base Case
✅ 2. 递归做“拆分”，排序发生在 merge 中
很多学生误以为排序在 mergeSort()实际上排序发生在merge()
✅ 3. 时间复杂度（必考）
- 每一层合并：
O(n)
- 层数：
log n
- 总复杂度：
O(n log n)
✅ 4. 空间复杂度
- 需要额外数组
- 空间复杂度：
O(n)
5. Merge Sort 的时间复杂度
- 无论数据是否有序
- Merge Sort 的执行时间 始终是 O(n log n)
6. 选择题练习
问题 1
在什么情况下，Merge Sort 会执行得更快？
A. 数据已经升序
B. 数据已经降序
C. 无论如何，时间都一样
✅ 正确答案：C
问题 2
以下哪种排序算法通常最快？
A. Selection Sort
B. Insertion Sort
C. Merge Sort
✅ 正确答案：C
四、4.17.3 Tracing Challenge（追踪挑战）
挑战 1：Merge Sort 追踪
给定数组：
要求：
- 写出每一次 拆分
- 写出每一次 合并
- 直到数组完全有序
挑战 2：Recursive Binary Search 追踪
给定有序数组：
调用：
要求写出：
- 每次检查的 middle 元素
- 每次递归的
start和end
- 一共检查了多少个元素？
- 如果用 Linear Search，需要检查多少个？
五、4.17 总结（AP 考试重点）
你现在应该掌握：
- 递归可以用于遍历
- String
- 数组
- ArrayList
- Binary Search
- 必须使用有序数据
- 可以用循环或递归实现
- 通常比 Linear Search 更高效
- Merge Sort
- 是递归排序算法
- 使用 Divide and Conquer
- 时间复杂度始终是 O(n log n)
AP CSA Practice
Unit 4.17 – Recursive Searching and Sorting
Part A：Multiple-Choice Questions
（每题 1 分）
Question 1
Which of the following is a required condition for using the binary search algorithm?
A. The array must contain no duplicate values
B. The array must be sorted
C. The array must be stored in an ArrayList
D. The array must have an even number of elements
✅ Correct Answer: B
Question 2
Which statement best describes why binary search is more efficient than linear search?
A. Binary search checks fewer elements by skipping random indices
B. Binary search always finds the target in one comparison
C. Binary search eliminates half of the remaining elements each step
D. Binary search uses recursion instead of iteration
✅ Correct Answer: C
Question 3
Consider the following recursive binary search method:
Which line represents a base case?
A.
int mid = (start + end) / 2;B.
if (arr[mid] == target)C.
return binarySearch(arr, start, mid - 1, target);D.
return binarySearch(arr, mid + 1, end, target);✅ Correct Answer: B
（
end < start 也是 base case，但选项中只有 B）Question 4
What will happen if the condition
if (end < start) is removed from the recursive binary search?A. The algorithm will still work correctly
B. The algorithm will run faster
C. The algorithm may never stop running
D. The algorithm will always return -1
✅ Correct Answer: C
Question 5
Which of the following best describes merge sort?
A. A sorting algorithm that repeatedly swaps adjacent elements
B. A recursive algorithm that divides the array and merges sorted subarrays
C. A sorting algorithm that inserts elements into their correct position
D. A recursive algorithm that searches for a target value
✅ Correct Answer: B
Question 6
What is the time complexity of merge sort in all cases?
A. O(n)
B. O(n²)
C. O(log n)
D. O(n log n)
✅ Correct Answer: D
Question 7
Under what condition does merge sort run faster?
A. When the array is already sorted
B. When the array is sorted in reverse order
C. When the array has no duplicate values
D. It always takes approximately the same time
✅ Correct Answer: D
Question 8
Which of the following sorting algorithms must use recursion?
A. Selection sort
B. Insertion sort
C. Merge sort
D. Bubble sort
✅ Correct Answer: C
Part B：Free-Response Questions (FRQ)
FRQ 1 – Recursive Binary Search (Tracing)
(6 points)
Given the following sorted array:
A recursive binary search is called as follows:
(a)
List the value of
mid and the element checked at each recursive call until the target is found.(b)
How many elements are checked in total?
(c)
How many elements would a linear search check in the worst case for the same target?
Scoring Guidelines / Sample Answer
(a)
- Call 1: start = 0, end = 8 → mid = 4 → element = 11
- Call 2: start = 5, end = 8 → mid = 6 → element = 17
- Call 3: start = 7, end = 8 → mid = 7 → element = 20
- Call 4: start = 8, end = 8 → mid = 8 → element = 22
(b)
4 elements checked
(c)
Linear search may check 9 elements in the worst case
FRQ 2 – Recursive Method Writing
(7 points)
Write a recursive method
countOccurrences that counts how many times a given target value appears in an array.Method signature:
The method should:
- Return
0whenindexis past the end of the array
- Use recursion to count occurrences
Sample Solution
FRQ 3 – Merge Sort Conceptual Understanding
(6 points)
(a)
Explain why merge sort is considered a divide-and-conquer algorithm.
(b)
What is the base case of merge sort?
(c)
Why does merge sort always run in O(n log n) time, regardless of the initial order of the data?
Scoring Guidelines / Sample Answer
(a)
Merge sort divides the array into smaller subarrays, recursively sorts them, and then merges them back together.
(b)
The base case occurs when the subarray has one or zero elements.
(c)
The array is always divided into halves (log n levels), and merging at each level processes all n elements.
- 作者:现代数学启蒙
- 链接:https://www.math1234567.com/article/recursive
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章
