漫畫：二分法系列篇（第一講）

• 2020 年 3 月 30 日
• 筆記

01 PART

愛吃香蕉的阿珂

不知道為什麼叫做愛吃香蕉的阿珂，難道不應該是愛吃香蕉的猴子么…或者愛吃隊友的露娜么？

第875題：阿珂喜歡吃香蕉。這裡有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警衛已經離開了，將在 H 小時後回來。 阿珂可以決定她吃香蕉的速度 K （單位：根/小時），每個小時，她將會選擇一堆香蕉，從中吃掉 K 根。

如果這堆香蕉少於 K 根，她將吃掉這堆的所有香蕉，然後這一小時內不會再吃更多的香蕉。珂珂喜歡慢慢吃，但仍然想在警衛回來前吃掉所有的香蕉。返回她可以在 H 小時內吃掉所有香蕉的最小速度 K（K 為整數）。

示例 1：

輸入: piles = [3,6,7,11], H = 8 輸出: 4

示例 2：

輸入: piles = [30,11,23,4,20], H = 5 輸出: 30

示例 3：

輸入: piles = [30,11,23,4,20], H = 6 輸出: 23

PS：建議大家停留個兩分鐘先想一想…直接拉下去看題解就沒什麼意思了。

02 PART

二分查找

十個二分九個錯，有大佬用 "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky" 形容二分查找，譯為「思路很簡單，細節是魔鬼」。該演算法在二戰前期就被提出來，但是直到肯尼迪遇刺才完成第一個沒有Bug的版本，中間耗時16年。

簡單複習一下二分查找。在最簡單的形式中，二分查找對具有指定左索引和右索引的連續序列進行操作。我們也稱之為查找空間。二分查找維護查找空間的左、右和中間指示符，並比較查找目標；如果條件不滿足或值不相等，則清除目標不可能存在的那一半，並在剩下的一半上繼續查找，直到成功為止。

舉例說明：比如你需要找1-100中的一個數字，你的目標是用最少的次數猜到這個數字。你每次猜測後，我會說大了或者小了。而你只需要每次猜測中間的數字，就可以將餘下的數字排除一半。

不管我心裡想的數字如何，你在7次之內都能猜到，這就是二分。每次篩選掉一半數據，所以也稱為折半查找。一般而言，對於包含n個元素的列表，用二分查找最多需要log2n步。

二分查找的一般實現如下：（給一個Java版本的，比較正派的一個程式碼，沒有用一些縮寫形式）

//JAVA  public int binarySearch(int[] array, int des) {      int low = 0, high = array.length - 1;      while (low <= high) {          int mid = low + (high - low) / 2;          if (des == array[mid]) {              return mid;          } else if (des < array[mid]) {              high = mid - 1;          } else {              low = mid + 1;          }      }      return -1;  }  

為什麼是一般實現？

1、根據邊界的不同（開閉區間調整），彈性調整low與high的值，以及循環的終止條件。

2、根據元素是否有重複值，以及是否需要找到重複值區間，對原演算法進行改進。

鄭重申明（讀我的文章必看）：

• 本系列所有教程都不會用到複雜的語言特性，大家無須擔心沒有學過相關語法，演算法思想才是最重要的！
• 作為學術文章，雖然風格可以風趣，但嚴謹，我是認真的。本文所有程式碼均在leetcode進行過測試運行。

03 PART

題目分析

簡單複習了二分查找，我們來看本題。

注意，絕大部分「在遞增遞減區間中搜索目標值」 的問題，都可以轉化為二分查找問題。並且，二分查找的題目，基本逃不出三種：找特定值，找大於特定值的元素（上界），找小於特定值的元素（下界）。

而根據這三種，程式碼又最終會轉化為以下這些問題：

• low、high 要初始化為 0、n-1 還是 0、n 又或者 1，n？
• 循環的判定條件是 low < high 還是 low <= high？
• if 的判定條件應該怎麼寫？if 條件正確時，應該移動哪邊的邊界？
• 更新 low 和 high 時，mid 如何處理？

處理好了上面的問題，自然就可以順利解決問題。將上面的思想代入到本題，我們要找 「阿珂在 H 小時吃掉所有香蕉的最小速度 K」。那最笨的就是阿珂吃的特別慢，每小時只吃掉 1 根香蕉，然後我們逐漸遞增阿珂吃香蕉的速度到 i，剛好滿足在 H 小時可以吃掉所有香蕉，此時 i 就是我們要找的最小速度。當然，我們沒有這麼笨，自然想到可以使用二分的思想來進行優化。

然後就簡單了，我們尋找二分查找模板中初始條件和終止條件（注意，這裡的 high、low、mid 都代表的是速度）：

//這裡我把最小速度定義成了1，可能大家會覺得奇怪，模板里不是0嗎？  //所以這裡我其實是想說，演算法千變萬化，大家不要生搬硬套。  //從字面理解，如果定義成0，意味著阿珂會選擇一個香蕉都不吃，難道阿珂傻？  var low = 1  //最大的速度，當然等於吃掉最大一堆的香蕉，畢竟一小時只能吃一堆，再大也沒有意義  var high = maxArr(piles)  //中間速度  var mid = (low + high) / 2  

//java  public class Solution {          public int minEatingSpeed(int[] piles, int H) {          int maxVal = 1;          for (int pile : piles) {              maxVal = Math.max(maxVal, pile);          }          int left = 1;          int right = maxVal;          while (left < right) {              int mid = (left + right) >> 1;              if (canEat(piles, mid, H)) {                  left = mid + 1;              } else {                  right = mid;              }          }          return left;      }        private boolean canEat(int[] piles, int speed, int H) {          int sum = 0;          for (int pile : piles) {              //向上取整              sum += (pile + speed - 1) / speed;          }          return sum > H;      }  }  

(看起來還是不錯的)

留下一個問題，假如我們的阿珂就是笨笨的，所以我們把 low 初始化為 0，此時的循環條件應該如何寫？if 條件如果成立，low 和 high 又該如何進行調整？