再谈二分查找

本文补充一些对二分查找的思考以及变体。

算法的核心

二分法的核心思想是有限有序的情况下能够快速找到目标值。这是一个很宽泛的条件，千万不要局限在数组这种数据结构中。很多情况下都可以使用二分，而不是一定要有一个数组然后对其进行排序才行。

详细说明下：

• 有限指的就是所有的可能性是有限的，可枚举的
• 有序指的是存在着线性的映射关系，即在有限的可能的取值中，每个值和目标值之间是线性关系
  只要满足上面两种情况，就可以用二分法。再抽象一下，只要存在这样一个函数y = f(x)，其中x的取值有限，且这个函数是单调的，就可以二分。

由此得出结论：判断一个问题能否用二分来解，做下面三步：

• 找到函数的表达式
• 确定是递增的
• 找到x的取值范围

  举例说明

有序数组找目标值

这是最常见的例子，此时的函数其实就是y=x

lc875 吃香蕉问题

这个题描述很多，尤其是题目内也给了一个数组，这很容易把人绕进去对数组排序做二分，这样是错的。

这个题确实可以二分来解。但一定要抓出二分的本质。

这个题可以看出：

• 要求的速度和完成的耗时是一个函数
• 这个函数是单调递减的（成反比）
• 速度的取值范围有限，最慢就是1，最快就是最多一堆香蕉的个数（再快没有意义了）
  完美满足二分，直接按二分去接就好。另外还有一点就是这个题不是求一个特定值，而是求边界，这是二分的拓展用法，下面详细叙述。

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int maxVal = 0;
        for(int i: piles){
            maxVal = Math.max(i,maxVal);
        }
        int l = 1;
        int r = maxVal;
        //此处右边界r是有意义的
        while(l<r){
            int mid = l+(r-l)/2;
            if(getTime(mid,piles)>h){
                l = mid+1;
            }else{
            //左边跳过，右边不跳过(不-1)，因为此时的右边届是满足的解，但再往左可能还有解
                r = mid;
            }
        }
        return r;
    }

    public int getTime(int speed, int[] piles){
        int res = 0;
        for(int i: piles){
            res += ((i/speed)+(i%speed == 0? 0: 1));
        }
        return res;
    }
}

拓展二分，从求值到求范围

类似lc34

如果要求范围，则当找到一个满足条件的解之后，如果这个解的左边还可能有其他解，则应该改右边界。如果判断这个解的右边还可能有解，则改动左边界。这样走两遍相当于找到了解的左边界和右边届

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        // find left
        while (l <= r) {
            System.out.println(l + " " + r);
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                res[0] = mid;
                r = mid - 1;
            }
        }
        // find right
        l = 0;
        r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                res[1] = mid;
                l = mid + 1;
            }
        }
        return res;
    }
}

固定写法，避免死循环

上一篇二分查找的文章详细说明了两种写法，左闭右开、左闭右闭。两种方法是等效的，重点是不要把两种的使用条件搞混，导致死循环或者漏掉边界值。

就记住固定一种就好，记住三个条件：**<=，r=n-1，左右都缩**