前面課時中，我們學習了遞歸的思想，它是一種函數自我調用縮小問題規模的方法。這一課時我們繼續學習另一種算法思維，分治法。 從定性的角度來看，分治法的核心思想就是“分而治之”。利用分而治之的思想，就可以把一個大規模、高難度的問題，分解為若干個小規模、低難度的小問題。隨后，開發者將面對多個簡單的問題，并很快地找到答案各個擊破。在把這些簡單問題解決好之后，我們通過把這些小問題的答案合并，就得到了原問題的答案。 分治法應用很廣泛，很多高效率的算法都是以分治法作為其基礎思想，例如排序算法中的快速排序和歸并排序。 #### 分治法是什么？ 計算機求解問題所需的計算時間，與其涉及的數據規模強相關。簡而言之，問題所涉及的數據規模越小，它所需的計算時間也越少；反之亦然。 我們來看一個例子：**在一個包含 n 個元素的無序數組中，要求按照從小到大的順序打印其 n 個元素**。 假設我們采用 n 個元素之間的兩兩比較的計算方法，去得到從小到大的序列。分析如下： 當數據量 n = 1 時，不需任何計算，直接打印即可； 當數據量 n = 2 時 ，那需要做 1 次比較即可達成目標； 當數據量 n = 3 時，要對這 3 個元素進行兩兩比較，共計 3 次比較； 而當數據量 n = 10 時，問題就不那么容易處理了，我們需要 45 次比較（計算方式是 0.5*n(n-1) ）。 因此，要想通過上述方法直接解決一個規模較大的問題，其實是相當困難的。 基于此，分治法的核心思想就是分而治之。具體來說，它先將一個難以直接解決的大問題，分割成一些可以直接解決的小問題。如果分割后的問題仍然無法直接解決，那么就繼續遞歸地分割，直到每個小問題都可解。 通常而言，這些子問題具備互相獨立、形式相同的特點。這樣，我們就可以采用同一種解法，遞歸地去解決這些子問題。最后，再將每個子問題的解合并，就得到了原問題的解。 #### 分治法的價值 關于分治法，很多同學都有這樣一個誤區。那就是，當你的計算機性能還不錯的時候，采用分治法相對于全局遍歷一遍沒有什么差別。 例如下面這個問題，在 1000 個有序數字構成的數組 a 中，判斷某個數字 c 是否出現過。 * 第一種方法，全局遍歷。 復雜度 O(n)。采用 for 循環，對 1000 個數字全部判斷一遍。 * 第二種方法，采用二分查找。 復雜度 O(logn)。遞歸地判斷 c 與 a 的中位數的大小關系，并不斷縮小范圍。 這兩種方法，對時間的消耗幾乎一樣。那分治法的價值又是什么呢？ 其實，在小數據規模上，分治法沒有什么特殊價值。無非就是讓代碼顯得更牛一些。只有在大數據集上，分治法的價值才能顯現出來。 下面我們通過一個經典的案例帶你感受分治法的價值。 **假如有一張厚度為 1 毫米且足夠柔軟的紙，問將它對折多少次之后，厚度能達到地球到月球的距離？** 這個問題看起來很異想天開。根據百度百科，地月平均距離是 384,403.9 千米，大約 39 萬千米。粗看怎么也需要對折 1 萬次吧？但實際上，根據計算，我們只需要對折 39 次就夠了。計算的過程是 2^39 = 549,755,813,888 = 55 萬千米 > 39 萬千米。那么，這個例子意味著什么呢？ 我們回到前面講到的在數組 a 中查找數字 c 的例子，如果數組 a 的大小拓展到 549,755,813,888 這個量級上，使用第二種的二分查找方法，僅僅需要 39 次判斷，就能找到最終結果。相比暴力搜索的方法，性能優勢高的不是一星半點！這也證明了，復雜度為 O(logn) 相比復雜度為 O(n) 的算法，在大數據集合中性能有著爆發式的提高。 #### 分治法的使用方法 前面我們講到分治法的核心思想是“分而治之”，當你需要采用分治法時，一般原問題都需要具備以下幾個特征： 1. 難度在降低，即原問題的解決難度，隨著數據的規模的縮小而降低。這個特征絕大多數問題都是滿足的。 2. 問題可分，原問題可以分解為若干個規模較小的同類型問題。這是應用分治法的前提。 3. 解可合并，利用所有子問題的解，可合并出原問題的解。這個特征很關鍵，能否利用分治法完全取決于這個特征。 4. 相互獨立，各個子問題之間相互獨立，某個子問題的求解不會影響到另一個子問題。如果子問題之間不獨立，則分治法需要重復地解決公共的子問題，造成效率低下的結果。 根據前面我們對分治法的分析，你一定能迅速聯想到遞歸。分治法需要遞歸地分解問題，再去解決問題。因此，分治法在每輪遞歸上，都包含了分解問題、解決問題和合并結果這 3 個步驟。 為了讓大家對分治法有更清晰地了解，我們以二分查找為例，看一下分治法如何使用。關于分治法在排序中的使用，我們會在第 11 課時中講到。查找問題指的是，在一個有序的數列中，判斷某個待查找的數字是否出現過。二分查找，則是利用分治法去解決查找問題。通常二分查找需要一個前提，那就是輸入的數列是有序的。 **二分查找的思路比較簡單，步驟如下**： 1. 選擇一個標志 i 將集合 L 分為二個子集合，一般可以使用中位數； 2. 判斷標志 L(i) 是否能與要查找的值 des 相等，相等則直接返回結果； 3. 如果不相等，需要判斷 L(i) 與 des 的大小； 4. 基于判斷的結果決定下步是向左查找還是向右查找。如果向某個方向查找的空間為 0，則返回結果未查到； 5. 回到步驟 1。 我們對二分查找的復雜度進行分析。二分查找的最差情況是，不斷查找到最后 1 個數字才完成判斷。那么此時需要的最大的復雜度就是 O(logn)。 #### 分治法的案例 下面我們一起來看一個例子。在數組 { 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; if (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); } } ``` 我們基于這個例子，可以對它進行一些經驗和規律的總結，這些經驗會輔助大家在面試時找到解題思路。 1. 二分查找的時間復雜度是 O(logn)，這也是分治法普遍具備的特性。當你面對某個代碼題，而且約束了時間復雜度是 O(logn) 或者是 O(nlogn) 時，可以想一下分治法是否可行。 2. 二分查找的循環次數并不確定。一般是達到某個條件就跳出循環。因此，編碼的時候，多數會采用 while 循環加 break 跳出的代碼結構。 3. 二分查找處理的原問題必須是有序的。因此，當你在一個有序數據環境中處理問題時，可以考慮分治法。相反，如果原問題中的數據并不是有序的，則使用分治法的可能性就會很低了。 以上 3 點經驗和規律的總結，可以幫助你快速找到解決方案，做好技術選型。在實際工作和參加面試時，都是非常重要的經驗。 #### 練習題 最后，我們給出一個進階的問題，供大家練習。題目如下： 在一個有序數組中，查找出第一個大于9的數字，假設一定存在。例如，arr = { -1, 3, 3, 7, 10, 14, 14 }; 則返回 10。 在這里提醒一下，帶查找的目標數字具備這樣的性質： 第一，它比 9 大； 第二，它前面的數字（除非它是第一個數字），比 9 小。 因此，當我們作出向左走或向右走的決策時，必須滿足這兩個條件。 ``` public static void main(String[] args) { int targetNumb = 9; // 目標有序數組 int[] arr = { -1, 3, 3, 7, 10, 14, 14 }; int middle = 0; int low = 0; int high = arr.length - 1; while (low <= high) { middle = (high + low) / 2; if (arr[middle] > targetNumb && (middle == 0 || arr[middle - 1] <= targetNumb)) { System.out.println("第一個比 " + targetNumb + " 大的數字是 " + arr[middle]); break; } else if (arr[middle] > targetNumb) { // 說明該數在low~middle之間 high = middle - 1; } else { // 說明該數在middle~high之間 low = middle + 1; } } } ``` #### 總結 分治法經常會用在海量數據處理中。這也是它顯著區別于遍歷查找方法的優勢。在面對陌生問題時，需要注意原問題的數據是否有序，預期的時間復雜度是否帶有 logn 項，是否可以通過小問題的答案合并出原問題的答案。如果這些先決條件都滿足，你就應該第一時間想到分治法。 最后，如果你在工作中，遇到了與分治法相關的困難或經驗，歡迎你在留言區和我分享。