Recursive Searching and Sorting
Introduced| English |
|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ |
| merge sort/mɜːdʒ sɔːt/ |
| merge/mɜːdʒ/ |
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.
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.
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.
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)).
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.
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².
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.
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].
Always take the smaller front element: 1, 2, 3, 4.