[数据结构与算法]力扣875. 爱吃香蕉的珂珂

二分搜索问题的应用

什么问题可以运用二分搜索算法技巧？

首先，你要从题目中抽象出一个自变量 x，一个关于 x 的函数 f(x)，以及一个目标值 target。

同时，x, f(x), target 还要满足以下条件：

1、f(x) 必须是在 x 上的单调函数（单调增单调减都可以）。

2、题目是让你计算满足约束条件 f(x) == target 时的 x 的值。

具体来说，想要用二分搜索算法解决问题，分为以下几步：

1、确定 x, f(x), target 分别是什么，并写出函数 f 的代码。

2、找到 x 的取值范围作为二分搜索的搜索区间，初始化 left 和 right 变量。

3、根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。

珂珂喜欢吃香蕉。这里有?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 <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/koko-eating-bananas
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目让求什么，就把什么设为自变量x

class Solution {
    int f(int[] piles,int x){
        int hour=0;
        for(int i=0;i<piles.length;i++){
            hour+=piles[i]/x;
            if(piles[i]%x!=0){
                hour++;
            }
        }
        return hour;
    }
    public int minEatingSpeed(int[] piles, int h) {
        int left=1;
        int right=1000000000;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(f(piles,mid)==h){
                right=mid-1;
            }
            else if(f(piles,mid)>h){
                left=mid+1;
            }
            else if(f(piles,mid)<h){
                right=mid-1;
            }
        }
        return left;
    }
}