漫画：二分法系列篇（第一讲）
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 输出: 23PS：建议大家停留个两分钟先想一想...直接拉下去看题解就没什么意思了。
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 又该如何进行调整？