二分答案算法

基本概念

将最值问题转换为判定

与二分查找的区别

二分查找：在一个已知的有序数据集上进行二分地查找

二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案

如何判断一个题是不是用二分答案做的

1、答案在一个区间内（一般情况下，区间会很大，暴力超时）

2、直接搜索不好搜，但是容易判断一个答案可行不可行

3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。

此外，可能还会有一个典型的特征：求...最大值的最小 、 求...最小值的最大。

1、求...最大值的最小，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让r=mid）

2、同样，求...最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让l=mid）

例题

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

提示：

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

思路：

比如：

• [6,4 ,5,2,4,3]，离开20h
• 假如说速度是5根/1h
• 1)6->1
• 2)1->0
• 然后休息
• 3)4->0
• 休息
• 有富余的时间就休息了，没富余时间继续吃下一堆
• 推下来5达标满足
• 然后推下来4也达标
• 要求速度尽量小还要达标
• 1不达标....2达标（所以答案是2）

• 速度最小就是1，而速度的最大值就是数组最大值因为就算定的越大（比数组最大值还大）都是1h内吃完，时间并没有任何变化
• 所以可以得到题目的答案（最小还达标）是在这个区间的
• 这个区间是单调性的：
• 速度变大花费的时间是越小的，比如说速度为6那么花费的时间是a小时，速度为7花费的时间是b小时，那么a >= b 的，也就是在最大中找最小
• 这道题就是速度越大越有可能达标，速度越小越不可能达标（比如说速度4是达标的，那么意味着速度5，6，7，8都是达标的），满足答案是单调的，所以能够通过对答案进行二分得到最终答案
• 对答案二分过程：
• 比如：1，2，3，4，5，6，7，8
• 第一次二分，检查4是否达标
• 如果4达标，及一个答案ans = 4,然后再1~3这个范围取一个更小的检查是否答案，因为题目要求的是最小还达标，如果2不达标，那么不计入答案,ans还是4，去3~3范围二分检查。
• 如果4不达标，那么意味着1~3都不达标，ans不记录答案去右侧二分，然后在5~8区间二分，6还不达标那么再在右侧二分，也就是7，8，发现7达标，记录答案ans = 7，那么在7的左侧二分，发现7的左侧已经没了，那么答案就是7了
• 那么我们需要一个check函数检查是否达标：
• 也就是检查用给的中间值的速度吃这堆香蕉花的时间。

具体代码讲解：

bool check(int* piles, int pilesSize, int h, int mid) {
    long int sum = 0;
    for (int i = 0; i < pilesSize; i++) {
 
        if (piles[i] % mid != 0) {
            sum += (piles[i] / mid) + 1;
        }
        else{
            sum+=piles[i]/mid;
        }
    }
    return sum <= h;
}
int minEatingSpeed(int* piles, int pilesSize, int h) {
    // 最小且达标的速度，范围[l,r]
    int l = 1;
    int r = 0;
    for (int i = 0; i < pilesSize; i++) {
        if (piles[i] >= r)
            r = piles[i];
    }
    //[l,r]不停的二分
    int ans = 0;
    while (l <= r) { // 直到二分范围消失
        int mid = (r + l) / 2;
        if (check(piles, pilesSize, h, mid)) {
            // 达标，记录答案
            // 左侧二分
            ans = mid;
            r = mid - 1;
        } else {
            // 不达标，不记答案
            // 右侧二分
            l = mid + 1;
        }
    }
    return ans;
}

410. 分割数组的最大值

题目

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。

设计一个算法使得这 k 个子数组各自和的最大值最小。

示例 1：

输入：nums = [7,2,5,10,8], k = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

示例 2：

输入：nums = [1,2,3,4,5], k = 2
输出：9

示例 3：

输入：nums = [1,4,4], k = 3
输出：4

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 106
• 1 <= k <= min(50, nums.length)

思路：

估计最终答案可能的范围

• 每部分累加和求出来的最大值尽量小（答案）
• 整个数组的和为A
• [0,A]
• 范围定得比较粗糙，可以定得特别粗糙，毕竟二分时间复杂度很低

分析问题的答案和给定条件之间的单调性

• 比如范围0~1000，对0~1000进行二分->500，相当于k份都要满足累加和<=500，
• 假如二分得600，也就是每一部分的累加和都<=600，那么条件放宽了，越有可能达标，
• 也就是答案越大越有可能，越小越不可能

建议一个check函数，当答案固定的情况下，判断给定的条件是否达标

• 根据题目建立check函数，在这道题当中check:
• 我们必须让数组每一份累加和满足<=mid，得到数组当中划分几部分可以满足这个要求，然后判断部分综合是否超过题目要求，超过了就是不达标没超过就是达标
• 比如[4,5,1,6,8,5,9]假如这时中间值是11，那么4+5+1小于11，如果加上6那么就多了，就开始装下一个part，起点从6开始。
• 但如果数组中有一个元素直接大于了给的中间值比如[3,3,77]假如给的中间值是15，77直接大于了15，那么我们要直接返回没有方案（即false）

在最终答案可能的范围上不断二分搜索，每次使用check函数判断，直到二分结束，找到最合适的答案

bool check(int* nums, int numsSize, int k, int mid) {
    // 必须让数组每一份的累加和满足<=mid,请问划分成几个部分才够
    // 一直加加到要超了，就停，代表一个子达成，
    // 但如果单点的值就超过，直接用整数最大值表示没有方案
    int parts = 1;
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > mid) {
            return false;
        }
        if (sum + nums[i] > mid) {
            parts++;
            sum = nums[i];
        } else {
            sum += nums[i];
        }
    }
    return parts <= k;
}
int splitArray(int* nums, int numsSize, int k) {
    long int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    long int ans = 0;
    long int l = 0;
    long int r = sum;
    //[0,ans]二分
    while (l <= r) {
        // 必须让数组每一份的累加和满足<=mid,请问划分成几个部分才够
        int mid = (l + r) / 2;
        if (check(nums, numsSize, k, mid)) {
            // 如果你需要的部分数量<=给你的部分的数量说明达标
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

总结

1. 估计最终答案可能的范围
2. 分析问题的答案和给定条件之间的单调性
3. 建议一个check函数，当答案固定的情况下，判断给定的条件是否达标
4. 在最终答案可能的范围上不断二分搜索，每次使用check函数判断，直到二分结束，找到最合适的答案
5. 核心：分析单调性，建立check函数