拆分、求解、合併
分治法是一份三步配方。分：把輸入拆成兩個或多個同類型的更小子問題。治：遞迴求解每個子問題（基準情形處理最小的那些片段）。合：把子答案拼成整體的答案。
- 分——把問題切成同樣形狀的更小子問題（通常是兩半）。
- 治——用遞迴解每個子問題；基準情形直接回答最小的片段。
- 合——把子答案組裝成完整答案（有時這是難點，有時則毫不費力）。
二分搜尋就是分治
你在基礎那一級已經見過二分搜尋。它是最簡單的分治：看有序陣列的中點，然後扔掉一半，在另一半上遞迴。這裡"分"是"取中點"，"治"是"在一側搜尋"，而"合"幾乎不存在——你遞迴進去的那一側就藏著答案。
// 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) + 工作量 涵蓋了大多數分治開銷；後面一級的主定理能一眼解出它。