漫画：二分法系列篇（第一讲）

• 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 又该如何进行调整？