二分搜索

没有重复元素的有序数组普通二分查找

重复元素的有序数组左侧边界的二分搜索，右侧边界的二分搜索

左侧边界的二分搜索

当target存在数组nums中时，返回的是第一个重复元素的索引

当target不存在数组nums中时

例：nums[]=[2,3,5,7] target=4 返回的left=2

left指向nums中大于target的最小元素索引
返回的是target应该插入的位置索引
返回nums数组中小于target的个数

右侧边界的二分搜索

返回的是最后一个重复元素的索引

二分搜索的应用

什么问题可以应用二分搜索？

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

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

f(x) 必须是在 x 上的单调函数（单调增单调减都可以）。
题目是让你计算满足约束条件 f(x) == target 时的 x 的值。

例：875. 爱吃香蕉的珂珂

分析：自变量x是珂珂吃香蕉的速度，f(x)是吃完所有堆上所用时间。 x越大，吃的越快，所花时间f(x)就越小。吃香蕉的时间限制H就是target.

x的左右边界如何确定？最小速度=1 最大速度堆上最大的香蕉个数使用左侧边界的二分搜索

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left=1;
        int right=maxV(piles);
        while(left<=right){
            int mid=left+(right-left)/2;
            if(f(piles,mid)==h){
                right=mid-1;
            }else if(f(piles,mid)<h){
                right=mid-1;
            }else if(f(piles,mid)>h){
                left=mid+1;
            }
        }
        return left;
    }
    // 速度为x时，吃完所有堆所需时间  递减可重复的有序序列
    public long f(int[] piles, int x){   // int类型不够
        long hours=0;
        for(int i=0;i<piles.length;i++){
            if(piles[i]%x==0){
                hours+=piles[i]/x;
            }else{
                hours=hours+1+piles[i]/x;
            }
        }
        return hours;
    }

    // 求堆中最大值
    public int maxV(int[] piles){
        int max=piles[0];
        for(int i=1;i<piles.length;i++){
            if(piles[i]>max){
                max=piles[i];
            }
        }
        return max;
    }
}