1. 分治法概念

分治，顧名思義，分而治之。

具體來說，它先將一個難以直接解決的大問題，分割成一些可以直接解決的小問題。如果分割后的問題仍然無法直接解決，那么就繼續遞歸地分割，直到每個小問題都可解。

分治法產生的子問題與原始問題相同，只是規模減小，反復使用分治方法，可以使得子問題的規模不斷減小，直到能夠被直接求解為止。

通常而言，這些子問題具備互相獨立、形式相同的特點。這樣，我們就可以采用同一種解法，遞歸地去解決這些子問題。最后，再將每個子問題的解合并，就得到了原問題的解。

2. 分治法前提

當你需要采用分治法時，一般原問題都需要具備以下幾個特征：

• 難度在降低，即原問題的解決難度，隨著數據的規模的縮小而降低。這個特征絕大多數問題都是滿足的。

• 問題可分，原問題可以分解為若干個規模較小的同類型問題。這是應用分治法的前提。

• 解可合并，利用所有子問題的解，可合并出原問題的解。這個特征很關鍵，能否利用分治法完全取決于這個特征。

• 相互獨立，各個子問題之間相互獨立，某個子問題的求解不會影響到另一個子問題。如果子問題之間不獨立，則分治法需要重復地解決公共的子問題，造成效率低下的結果。

能使用分治法解決的問題一般都具有兩個顯著的特點：

1. 是問題可以分解為若干個規模較小的相同問題，并且這個分解關系可以用遞歸或遞推的方式逐級分解，直到問題的規模小到可以直接求解的程度。

2. 是子問題的解可以用某種方式合并出原始問題的解。這很容易理解，如果不能合并出原始問題的解，那么子問題的劃分和求解就沒有意義了。

2. 分治法步驟

• 分解：

將問題分解為若干個規模較小，相互獨立且與原問題形式相同的子問題，確保各個子問題的解具有相同的子結構。

• 解決：

如果上一步分解得到的子問題可以解決，則解決這些子問題，否則，對每個子問題使用和上一步相同的方法再次分解，然后求解分解后的子問題，這個過程可能是一個遞歸的過程。

• 合并：

將上一步解決的各個子問題的解通過某種規則合并起來，得到原問題的解。

3. 遞歸實現分治法

遞歸作經常和分治法一起使用，因為問題的分解肯定不是一步到位，往往需要反復使用分治手段，在多個層次上層層分解，這種分解的方法很自然地導致了遞歸方式的使用。

從算法實現的角度看，分治法得到的子問題和原問題是相同的，當然可以用相同的函數來解決，區別只在于問題的規模和范圍不同。通過特定的函數參數安排，使得同一個函數可以解決不同規模的相同問題，這就是遞歸方法的基礎。

4. 分治法案例

在數組 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } 中，查找 8 是否出現過。

首先判斷 8 和中位數 5 的大小關系。因為 8 更大，所以在更小的范圍 6, 7, 8, 9, 10 中繼續查找。此時更小的范圍的中位數是 8。由于 8 等于中位數 8，所以查找到并打印查找到的 8 對應在數組中的 index 值。

從代碼實現的角度來看，我們可以采用兩個索引 low 和 high ，確定查找范圍。最初 low 為 0，high 為數組長度減 1。在一個循環體內，判斷 low 到 high 的中位數與目標變量 targetNumb 的大小關系。根據結果確定向左走 high = middle - 1 或者向右走 low = middle + 1 ，來調整 low 和 high 的值。直到 low 反而比 high 更大時，說明查找不到并跳出循環。

我們給出代碼如下：

public static void main(String[] args) {// 需要查找的數字int targetNumb = 8;// 目標有序數組int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };int middle = 0;int low = 0;int high = arr.length - 1;int isfind = 0;while (low <= high){middle = (high + low) / 2;	// high + low容易造成溢出，使用 low + (high - low) / 2if (arr[middle] == targetNumb) {System.out.println(targetNumb + " 在數組中,下標值為: " + middle);isfind = 1;break;} else if (arr[middle] > targetNumb) {// 說明該數在low~middle之間high = middle - 1;} else {// 說明該數在middle~high之間low = middle + 1;}}if (isfind == 0) {System.out.println("數組不含 " + targetNumb);}
}

5. 規律總結

• 二分查找的時間復雜度是 O(logn) ，這也是分治法普遍具備的特性。當你面對某個代碼題，而且約束了時間復雜度是 O(logn) 或者是 O(nlogn) 時，可以想一下分治法是否可行。
• 二分查找的循環次數并不確定。一般是達到某個條件就跳出循環。因此，編碼的時候，多數會采用 while 循環加 break 跳出的代碼結構。
• 二分查找處理的原問題必須是有序的。因此，當你在一個有序數據環境中處理問題時，可以考慮分治法。相反，如果原問題中的數據并不是有序的，則使用分治法的可能性就會很低了。

4. 實例

字符串全排列問題：
給定一個沒有重復字母的字符串，輸出該字符串中字符的所有排列。假如給定的字符串是“abc”，則應該輸出“abc”、“acb”、“bac”、“bca”、“cab”和“cba”六種結果。

總結

以上是生活随笔為你收集整理的算法设计思想（4）— 分治法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。