拆分、求解、合并
分治法是一份三步配方。分：把输入拆成两个或多个同类型的更小子问题。治：递归求解每个子问题（基准情形处理最小的那些片段）。合：把子答案拼成整体的答案。
- 分——把问题切成同样形状的更小子问题（通常是两半）。
- 治——用递归解每个子问题；基准情形直接回答最小的片段。
- 合——把子答案组装成完整答案（有时这是难点，有时则毫不费力）。
二分查找就是分治
你在基础那一级已经见过二分查找。它是最简单的分治：看有序数组的中点，然后扔掉一半，在另一半上递归。这里"分"是"取中点"，"治"是"在一侧查找"，而"合"几乎不存在——你递归进去的那一侧就藏着答案。
// search target in sorted a[lo..hi]; returns index or -1
int bsearch(const int a[], int lo, int hi, int target) {
if (lo > hi) return -1; // base case: empty range
int mid = lo + (hi - lo) / 2; // divide
if (a[mid] == target) return mid;
if (a[mid] < target)
return bsearch(a, mid + 1, hi, target); // conquer right half
else
return bsearch(a, lo, mid - 1, target); // conquer left half
}归并排序预演了这个模式
排序是头号例子。归并排序把数组分成两半，递归地排好每一半，然后把两个有序半段归并成一个。与二分查找不同，这里的合并步骤要做真正的工作——魔法就在那次归并里。下一篇你会完整实现它；这里先看它的形状。
[ 5 2 8 1 ] <- divide
/ \
[ 5 2 ] [ 8 1 ] <- divide again
/ \ / \
[5] [2] [8] [1] <- base case: length-1 is sorted
\ / \ /
[ 2 5 ] [ 1 8 ] <- combine (merge)
\ /
[ 1 2 5 8 ] <- final merge长度为 1 的数组本就是有序的——这就是基准情形。其余的一切就是分（对半拆）和合（归并）。记住这个形状；完整代码在下一篇，而同样的骨架会在快速排序里以不同的拆分步骤重现。
为什么它会产生递推式
因为分治算法用它自身的更小副本来描述自己的开销，它的运行时间天然写成递推关系——一个让 T(n) 引用 T(更小的某值) 的方程。
- 二分查找：T(n) = T(n/2) + O(1)——只走一半，常数级合并。解得 O(log n)。
- 归并排序：T(n) = 2T(n/2) + O(n)——两半，线性归并。解得 O(n log n)。
- 模式 T(n) = aT(n/b) + 工作量 覆盖了大多数分治开销；后面一级的主定理能一眼解出它。