二分搜素相信大家都很熟悉，典型的二分搜索题型有：『寻找一个相等值』『寻找最左相等元素』『寻找最右相等元素』，关于这三种典型的二分搜索分析可见 二分搜索
其实还有一种旋转类的二分搜索，详情可见 浅析：搜索旋转排序数组
上述介绍的类型基本上都很明显的可以一眼看出「搜索对象」和「搜索范围」
举个例子：[1, 2, 3, 4, 4, 5], target = 4，要求：寻找最左相等元素
其实这两个概念对于「典型的二分搜索」来说在意义上有一丢丢的重叠，即：确定了搜索对象，不就直接可以得到搜索范围嘛，这两个存在一定的等价性
可是可是可是，这两个概念在本篇文章要介绍的「抽象类的二分搜索」中有很重要的作用！！接着往下看就完事啦，哈哈哈哈哈
「寻找最左/右相等元素」详细内容可见 二分搜索
这一部分只是简单的梳理一下这种类型的框架，只梳理「寻找最左相等元素」，「寻找最右相等元素」同理
private int leftBound(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mid = lo - (lo - hi) / 2; // 「找到」或者「比目标值大」均向左收缩 if (nums[mid] >= target) hi = mid - 1; else lo = mid + 1; } // 结束情况 : lo = hi + 1 // 未找到的情况 if (lo == nums.length || nums[lo] != target) return -1; return lo;}为什么对于找到元素的情况，最后返回lo就是正确下标呢？？？？
原因：首先，结束循环的条件为lo = hi + 1；如果找到了相等元素，此时循环内的mid就是正确下标；而由于收缩，hi = mid - 1，刚好比正确下标少 1。所以lo刚好是正确下标
题目详情可见 爱吃香蕉的珂珂
第一眼看到这个题目，是不是都看不出是个二分搜索的题目！！所以才说它是抽象类的二分搜索嘛，需要我们自己把模型剥离出来
一般这种抽象类的二分搜索建议从问题入手，原问题：「返回她可以在h小时内吃掉所有香蕉的最小速度k」
对于一个给定的速度v，如果该速度慢了，那我们就「向右收缩」；如果该速度快了，那我们就「向左收缩」；如果该速度满足要求，那我们能不能找一个更小的且满足要求的速度，所以需要继续「向左收缩」(是不是很像「寻找最左相等元素」？自信点，就是「寻找最左相等元素」)
所以「搜索对象」是什么？？很明显就是「速度」嘛！！
那「搜索范围」又是什么呢？？
0或者1，0 一看就没有意义嘛 (每小时吃 0 个，吃到猴年马月也吃不完呀呀！！)，所以范围的下界是 1Integer.MAX_VALUE嘛，显然这个最大值也没有意义 (每小时最多吃一堆，你速度再快，吃完一堆，你也得干等着！！！)，所以范围的上界是n堆香蕉的最大值明确了「搜索对象」和「搜索范围」，我们还需要搞清楚怎么确定速度慢了还是快了，肯定要有一个参考对象才能确定慢还是快嘛
很聪明，这个参考对象就是题目给的h小时。如果我们以速度v开吃，需要的时间为t，如果t < h说明速度快了；如果t > h说明速度慢了
现在我们就可以开始干正事 (二分搜索) 了
xxxxxxxxxxpublic int minEatingSpeed(int[] piles, int h) { // lo 范围的下界，hi 范围的上界 int lo = 1, hi = 1; for (int p : piles) hi = Math.max(p, hi); // 二分搜索 while (lo <= hi) { int speed = lo - (lo - hi) / 2, t = 0; // 求所需时间 for (int p : piles) { if (p % speed != 0) t++; t += p / speed; } // 速度快了 或者 速度满足要求，向左收缩 if (t <= h) hi = speed - 1; // 速度慢了， 向右收缩 else lo = speed + 1; } return lo;}至于为什么最后返回lo，上面有详细分析！！
至于为什么不用考虑「未找到的情况」，根据题目给出的范围，一定可以找到一个满足要求的速度
题目详情可见 在 D 天内送达包裹的能力
首先找到原问题「返回能在days天内将传送带上的所有包裹送达的船的最低运载能力」
对于一个给定的运载能力capacity，如果该运载能力低了，那我们就「向右收缩」；如果该运载能力高了，那我们就「向左收缩」；如果该运载能力满足要求，那我们能不能找一个更低的且满足要求的运载能力，所以需要继续「向左收缩」(是不是很像「寻找最左相等元素」？自信点，就是「寻找最左相等元素」)
所以「搜索对象」是什么？？很明显就是「运载能力」嘛！！
那「搜索范围」又是什么呢？？
Integer.MAX_VALUE明确了「搜索对象」和「搜索范围」，我们还需要搞清楚怎么确定运载能力低了还是高了，肯定要有一个参考对象才能确定低还是高嘛
很聪明，这个参考对象就是题目给的days天。如果我们以运载能力capacity运输，需要的时间为t，如果t < days说明运载能力高了；如果t > days说明运载能力低了
现在我们就可以开始干正事 (二分搜索) 了
xxxxxxxxxxpublic int shipWithinDays(int[] weights, int days) { // lo 范围的下界，hi 范围的上界 int lo = 1, hi = Integer.MAX_VALUE; for (int w : weights) lo = Math.max(lo, w); // 二分搜索 while (lo <= hi) { int capacity = lo - (lo - hi) / 2; // 获得所需天数 int t = getDays(weights, capacity); // 运载能力高了 或者 运载能力满足要求，向左收缩 if (t <= days) hi = capacity - 1; // 运载能力低了， 向右收缩 else lo = capacity + 1; } return lo;}// 返回以运载能力 capacity 运输需要的天数private int getDays(int[] weights, int capacity) { int sum = 0, day = 1; for (int w : weights) { if (sum + w > capacity) { sum = 0; day++; } sum += w; } return day;}题目详情可见 分割数组的最大值
首先找到原问题「使得这m个子数组各自和的最大值最小」
对于一个给定的最大值max，如果该最大值小了，那我们就「向右收缩」；如果该最大值大了，那我们就「向左收缩」；如果该最大值满足要求，那我们能不能找一个更小的且满足要求的最大值，所以需要继续「向左收缩」(是不是很像「寻找最左相等元素」？自信点，就是「寻找最左相等元素」)
所以「搜索对象」是什么？？很明显就是「最大值」嘛！！
那「搜索范围」又是什么呢？？
Integer.MAX_VALUE明确了「搜索对象」和「搜索范围」，我们还需要搞清楚怎么确定最大值小了还是大了，肯定要有一个参考对象才能确定小还是大嘛
很聪明，这个参考对象就是题目给的m个子数组。如果我们以最大值max分解数组，可以分解成非空连续子数组的数量为cnt，如果cnt < m说明最大值大了；如果cnt > m说明最大值小了
现在我们就可以开始干正事 (二分搜索) 了
xxxxxxxxxxpublic int splitArray(int[] nums, int m) { // lo 范围的下界，hi 范围的上界 int lo = 0, hi = Integer.MAX_VALUE; for (int n : nums) lo = Math.max(lo, n); // 二分搜索 while (lo <= hi) { int max = lo - (lo - hi) / 2; // 获得非空连续子数组的数量 int cnt = getCnt(nums, max); // 最大值大了 或者 最大值满足要求，向左收缩 if (cnt <= m) hi = max - 1; // 最大值小了， 向右收缩 else lo = max + 1; } return lo;}// 返回以最大值 max 分解成非空连续子数组的数量private int getCnt(int[] nums, int max) { int cnt = 1, sum = 0; for (int n : nums) { if (sum + n > max) { cnt++; sum = 0; } sum += n; } return cnt;}是不是看了三个实战题目，发现「搜索对象」和「搜索范围」还挺重要滴！！没有骗你叭
相信大家看了上面三个题目的分析过程，对这一类题目已经有一些感觉了，下面来梳理一下解题思路
好了，大功告成！！！！