讀完本文，你不僅學會了演算法套路，還可以順便去 LeetCode 上拿下如下題目：
410.分割陣列的最大值
-----------
經常有讀者問我，讀了之前的爆文 二分查詢框架詳解 之後，二分查詢的演算法他寫的很溜了，但僅僅侷限於在陣列中搜索元素，不知道底怎麼在演算法題裡面運用二分查詢技巧來最佳化效率。
那我先說結論，你想用二分查詢技巧最佳化演算法，首先要把 for 迴圈形式的暴力演算法寫出來，如果演算法中存在如下形式的 for 迴圈：
// func(i) 是 i 的單調函式（遞增遞減都可以）int func(int i);// 形如這種 for 迴圈可以用二分查詢技巧最佳化效率for (int i = 0; i < n; i++) { if (func(i) == target) return i;}如果 func(i) 函式是在 i 上單調的函式，一定可以使用二分查詢技巧最佳化 for 迴圈。
「在 i 上單調的函式」是指 func(i) 的返回值隨著 i 的增加而增加，或者隨著 i 的增加而減小。
為什麼滿足這個條件就可以使用二分查詢？因為這個邏輯和「在有序陣列中查詢一個元素」是完全一樣的呀！
在有序陣列 nums 中查詢某一個數 target，是不是最簡單二分查詢形式？我們看下普通的 for 迴圈遍歷演算法：
// nums 是一個有序陣列int[] nums;// target 是要搜尋的元素int target;// 搜尋 target 在 nums 中的索引for (int i = 0; i < nums.length; i++) { if (nums[i] == target) return i;}既然 nums 是有序陣列，你把 nums[i] 看做函式呼叫，是不是可以理解為 nums 在引數 i 上是單調的？這是不是和之前說的 func(i) 函式完全一樣？
當然，前文 二分查詢框架詳解 說過，二分查詢演算法還有搜尋左側、右側邊界的變體，怎麼運用到具體演算法問題中呢？
還是注意觀察 for 迴圈形式，只是不一定是 func(i) == target 作為終止條件，可能是 <= 或者 >= 的關係，這個可以根據具體的題目意思來推斷，我們實操一下力扣第 410 題「分割陣列的最大值」，難度 Hard：
函式簽名如下：
int splitArray(int[] nums, int m);這個題目有點類似前文一道經典動態規劃題目 高樓扔雞蛋，題目比較繞，又是最大值又是最小值的。
簡單說，給你輸入一個數組 nums 和數字 m，你要把 nums 分割成 m 個子陣列。
肯定有不止一種分割方法，每種分割方法都會把 nums 分成 m 個子陣列，這 m 個子陣列中肯定有一個和最大的子陣列對吧。
我們想要找一個分割方法，該方法分割出的最大子陣列和是所有方法中最大子陣列和最小的。
請你的演算法返回這個分割方法對應的最大子陣列和。
我滴媽呀，這個題目看了就覺得 Hard，完全沒思路，這題怎麼能和二分查詢演算法扯上關係？
說個小插曲，快手面試有一道畫師畫畫的演算法題，很難，就是以這道題為原型。當時我沒做過這道力扣題，面試有點懵，不過之前文章 二分查詢演算法運用 寫了兩道類似的比較簡單的題目，外加面試官的提示，把那道題做出來了。
面試做演算法題的時候，題目一般都會要求演算法的時間複雜度，如果你發現 O(NlogN) 這樣存在對數的複雜度，一般都要往二分查詢的方向上靠，這也算是個小套路。
言歸正傳，如何解決這道陣列分割的問題？
首先，一個拍腦袋的思路就是用 回溯演算法框架 暴力窮舉唄，我簡單說下思路：
你不是要我把 nums 分割成 m 個子陣列，然後計算巴拉巴拉又是最大又是最小的那個最值嗎？那我把所有分割方案都窮舉出來，那個最值肯定可以算出來對吧？
怎麼窮舉呢？把 nums 分割成 m 個子陣列，相當於在 len(nums) 個元素的序列中切 m - 1 刀，對於每兩個元素之間的間隙，我們都有兩種「選擇」，切一刀，或者不切。
你看，這不就是標準的回溯暴力窮舉思路嘛，我們根據窮舉結果去計算每種方案的最大子陣列和，肯定可以算出答案。
但是回溯的缺點就是複雜度很高，我們剛才說的思路其實就是「組合」嘛，時間複雜度就是組合公式：
時間複雜度其實是非常高的，所以回溯演算法不是一個好的思路，還是得上二分查詢技巧，反向思考這道題。
現在題目是固定了 m 的值，讓我們確定一個最大子陣列和；所謂反向思考就是說，我們可以反過來，限制一個最大子陣列和 max，來反推最大子陣列和為 max 時，至少可以將 nums 分割成幾個子陣列。
比如說我們可以寫這樣一個 split 函式：
// 在每個子陣列和不超過 max 的條件下，// 計算 nums 至少可以分割成幾個子陣列int split(int[] nums, int max);比如說 nums = [7,2,5,10]，若限制 max = 10，則 split 函式返回 3，即 nums 陣列最少能分割成三個子陣列，分別是 [7,2],[5],[10]。
那如果我們找到一個最小 max 值，滿足 split(nums, max) 和 m 相等，那麼這個 max 值不就是符合題意的「最小的最大子陣列和」嗎？
現在就簡單了，我們只要對 max 進行窮舉就行，那麼最大子陣列和 max 的取值範圍是什麼呢？
顯然，子陣列至少包含一個元素，至多包含整個陣列，所以「最大」子陣列和的取值範圍就是閉區間 [max(nums), sum(nums)]，也就是最大元素值到整個陣列和之間。
那麼，我們就可以寫出如下程式碼：
/* 主函式，計算最大子陣列和 */int splitArray(int[] nums, int m) { int lo = getMax(nums), hi = getSum(nums); for (int max = lo; max <= hi; max++) { // 如果最大子陣列和是 max， // 至少可以把 nums 分割成 n 個子陣列 int n = split(nums, max); // 為什麼是 <= 不是 == ？ if (n <= m) { return max; } } return -1;}/* 輔助函式，若限制最大子陣列和為 max，計算 nums 至少可以被分割成幾個子陣列 */int split(int[] nums, int max) { // 至少可以分割的子陣列數量 int count = 1; // 記錄每個子陣列的元素和 int sum = 0; for (int i = 0; i < nums.length; i++) { if (sum + nums[i] > max) { // 如果當前子陣列和大於 max 限制 // 則這個子陣列不能再新增元素了 count++; sum = nums[i]; } else { // 當前子陣列和還沒達到 max 限制 // 還可以新增元素 sum += nums[i]; } } return count;}// 計算陣列中的最大值int getMax(int[] nums) { int res = 0; for (int n : nums) res = Math.max(n, res); return res;}// 計算陣列元素和int getSum(int[] nums) { int res = 0; for (int n : nums) res += n; return res;}這段程式碼有兩個關鍵問題：
1、對 max 變數的窮舉是從 lo 到 hi 即從小到大的。
這是因為我們求的是「最大子陣列和」的「最小值」，且 split 函式的返回值有單調性，所以從小到大遍歷，第一個滿足條件的值就是「最小值」。
2、函式返回的條件是 n <= m，而不是 n == m。按照之前的思路，應該 n == m 才對吧？
其實，split 函式採用了貪心的策略，計算的是 max 限制下至少能夠將 nums 分割成幾個子陣列。
舉個例子，輸入 nums = [2,1,1], m = 3，顯然分割方法只有一種，即每個元素都認為是一個子陣列，最大子陣列和為 2。
但是，我們的演算法會在區間 [2,4] 窮舉 max，當 max = 2 時，split 會算出 nums 至少可以被分割成 n = 2 個子陣列 [2] 和 [1,1]。
當 max = 3 時算出 n = 2，當 max = 4 時算出 n = 1，顯然都是小於 m = 3 的。
所以我們不能用 n == m 而必須用 n <= m 來找到答案，因為如果你能把 nums 分割成 2 個子陣列（[2],[1,1]），那麼肯定也可以分割成 3 個子陣列（[2],[1],[1]）。
好了，現在 for 迴圈的暴力演算法已經寫完了，但是無法透過力扣的判題系統，會超時。
由於 split 是單調函式，且符合二分查詢技巧進行最佳化的標誌，所以可以試圖改造成二分查詢。
那麼應該使用搜索左側邊界的二分查詢，還是搜尋右側邊界的二分查詢呢？這個還是要看我們的演算法邏輯：
int lo = getMax(nums), hi = getSum(nums);for (int max = lo; max <= hi; max++) { int n = split(nums, max); if (n <= m) { return max; }}可能存在多個 max 使得 split(nums, max) 算出相同的 n，因為我們的演算法會返回最小的那個 max，所以應該使用搜索左側邊界的二分查詢演算法。
現在，問題變為：在閉區間 [lo, hi] 中搜索一個最小的 max，使得 split(nums, max) 恰好等於 m。
那麼，我們就可以直接套用搜索左側邊界的二分搜尋框架改寫程式碼：
int splitArray(int[] nums, int m) { // 一般搜尋區間是左開右閉的，所以 hi 要額外加一 int lo = getMax(nums), hi = getSum(nums) + 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; // 根據分割子陣列的個數收縮搜尋區間 int n = split(nums, mid); if (n == m) { // 收縮右邊界，達到搜尋左邊界的目的 hi = mid; } else if (n < m) { // 最大子陣列和上限高了，減小一些 hi = mid; } else if (n > m) { // 最大子陣列和上限低了，增加一些 lo = mid + 1; } } return lo;}int split(int[] nums, int max) {/* 見上文 */}int getMax(int[] nums) {/* 見上文 */}int getSum(int[] nums) {/* 見上文 */}這段二分搜尋的程式碼就是標準的搜尋左側邊界的程式碼框架，如果不理解可以參見前文 二分查詢框架詳解，這裡就不展開了。
至此，這道題就透過二分查詢技巧高效解決了。假設 nums 元素個數為 N，元素和為 S，則 split 函式的複雜度為 O(N)，二分查詢的複雜度為 O(logS)，所以演算法的總時間複雜度為 O(N*logS)。