Recursive Searching and Sorting · 递归查找与排序
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | 分治 | fēn zhì |
| merge sort/mɜːdʒ sɔːt/ | 归并排序 | guī bìng pái xù |
| merge/mɜːdʒ/ | 合并 | hé bìng |
Recursion meets search and sort
- The same divide-and-conquer 分治 idea powers recursive binary search and merge sort 归并排序.
- Split the problem in half, solve the halves, combine.
- Recursive binary search searches one half by calling itself on it.
- Merge sort sorts each half, then merges the sorted halves together.
递归遇上查找与排序
- 同样的分治思想驱动递归二分查找和归并排序。
- 把问题分成两半，解决两半，再合并。
- 递归二分查找通过在一半上调用自己来查找那一半。
- 归并排序先对每一半排序，然后把已排序的两半合并到一起。
Recursive binary search
- Base case: an empty range means the target is not found.
- Look at the middle. If it's the target, return its index.
- If the target is smaller, recurse on the left half; if larger, the right half.
- Each call halves the range — the same
O(log n), written recursively.
递归二分查找
- 基准情形：一个空范围意味着目标未找到。
- 看中间。若它就是目标，返回它的下标。
- 若目标更小，在左半上递归；若更大，在右半上。
- 每次调用把范围减半——同样的
O(log n)，用递归写出来。
Merge sort
- Split the array into two halves; sort each half recursively.
- Base case: an array of 0 or 1 element is already sorted.
- Merge 合并: walk both sorted halves, always taking the smaller front element.
- Much faster than the
n²sorts — aboutn log nwork.
归并排序
- 把数组分成两半；对每一半递归排序。
- 基准情形：一个 0 个或 1 个元素的数组已经有序。
- 合并：走过两个已排序的半，总是取更小的前端元素。
- 比
n²的排序快得多——约n log n的工作量。
Why divide-and-conquer wins
- Halving the problem each step gives the
log nfactor. - Merge sort's
n log nbeats selection/insertion sort'sn²on large arrays. - The base case (empty or one element) stops every branch.
- Same shape as all recursion: split down, combine back up.
分治为何取胜
- 每步把问题减半带来那个
log n因子。 - 归并排序的
n log n在大数组上胜过选择/插入排序的n²。 - 基准情形（空或一个元素）停止每一个分支。
- 与所有递归同样的形状：向下分，向上合。
Recursive binary search recurses on ONE half (the target is only on one side); merge sort recurses on BOTH halves and then merges them. Both need a base case — an empty range means "not found" for search; a 0-or-1-element array is already sorted for merge sort. Divide-and-conquer is what makes them fast (O(log n) and O(n log n)).
递归二分查找在一半上递归（目标只在一侧）；归并排序在两半**上递归然后把它们合并。**两者都需要基准情形——对查找，空范围意味着“未找到”；对归并排序，0 个或 1 个元素的数组已经有序。分治正是让它们快的原因（O(log n) 和 O(n log n)）。
Merge-sorting [3, 1, 2, 4]:
- Split into
[3, 1]and[2, 4]; sort each →[1, 3]and[2, 4]. - Merge: take 1, then 2, then 3, then 4 →
[1, 2, 3, 4]. - Each merge picks the smaller front element in turn.
对 [3, 1, 2, 4] 做归并排序：
- 分成
[3, 1]和[2, 4]；各自排序 →[1, 3]和[2, 4]。 - 合并：取 1，再取 2，再取 3，再取 4 →
[1, 2, 3, 4]。 - 每次合并轮流挑更小的前端元素。
Recursive binary search recurses on one half (base case: empty range = not found) for O(log n) search. Merge sort recurses on both halves and merges them (base case: 0 or 1 element) for O(n log n) sorting. Both are divide-and-conquer: split down, combine back up — much faster than n².
递归二分查找在一半上递归（基准情形：空范围 = 未找到），做 O(log n) 查找。归并排序在两半上递归并把它们合并（基准情形：0 或 1 个元素），做 O(n log n) 排序。两者都是分治：向下分，向上合——比 n² 快得多。
Merge sort splits into halves, then merges up · 归并排序分成两半，再向上合并
Single elements are sorted (base case); merges combine them upward. · 单个元素已有序（基准情形）；合并把它们向上组合。
Recursive binary search recurses on... · 递归二分查找在……上递归。
The target is only on one side of the middle. · 目标只在中间的一侧。
Merge sort recurses on... · 归并排序在……上递归。
Sort each half, then merge the two sorted halves. · 对每一半排序，再合并两个已排序的半。
The base case for merge sort is an array of... · 归并排序的基准情形是一个……的数组。
One (or zero) element needs no sorting. · 一个（或零个）元素无需排序。
Merge sort's running time is about... · 归并排序的运行时间约为……
log n levels of splitting, n work per level. · log n 层拆分，每层 n 的工作量。
Both recursive binary search and merge sort are divide-and-conquer algorithms. · 递归二分查找和归并排序都是分治算法。
Both split the problem in half and recurse. · 两者都把问题分半并递归。
Order the merge step for halves [1,3] and [2,4]. · 给对半 [1,3] 和 [2,4] 的合并步骤排序。
Always take the smaller front element: 1, 2, 3, 4. · 总是取更小的前端元素：1, 2, 3, 4。