二分搜索怎么用？我又总结了套路 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：二分搜索怎么用？我又总结了套路

评论礼仪 见这里，违者直接拉黑。

[process-sk]

东哥，int right = ... + 1;这个如果我不加一使用闭区间的时候为什么不正确呢

[SuperCoder1999]

同问

[scutljh]

对于闭区间[left,right]，需要明白它的循环不变量是什么，因为是闭区间，因此left到right的每一个点都能被取到，因此在循环条件上首先就必须满足这个区间的定义，也就是while(left<=right)，它是成立的。再看缩区间，if(nums[middle]>target)，缩右边界，这是毋庸置疑的，right=mid还是mid-1？回归对区间的定义，左闭右闭的区间，已经判断nums[mid]不符合要求，接下来一定不要包含nums[middle]，区间自然是mid-1，如果等于mid，那你把一个不是搜索区间内的数放进来，最后就会死循环。若缩左边界left毋庸置疑也是mid+1

[saibeach]

Python Banana
啥也不说了， 谢labuladong

    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def f(piles, x):
            hours = 0
            for i in range(len(piles)):
                hours += piles[i] // x
                if piles[i]%x>0:
                    hours += 1
                    
            return hours
        
        left = 1
        right = max(piles)
        
        while left < right:
            mid = (right+left) // 2
            
            if f(piles, mid) <= h:
                right = mid
            else:
                left = mid + 1
                
        return right

[lovelyJason]

为啥js代码这段没过提交，我寻思着和那段java代码不是一样的吗， 珂珂吃香蕉那个题目

var minEatingSpeed = function(piles, h) {
    let left = 1
    let right = 1000000000 + 1
    while(left < right) {
        let mid = Math.floor(left + (right - left) / 2)
        console.log(left, right, f(piles, mid))
        if(f(piles, mid) <= h) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
    // 定义：速度为 x 时，需要 f(x) 小时吃完所有香蕉
    // f(x) 随着 x 的增加单调递减
    function f(piles, x) {
        let hours = 0
        for(let i = 0;i < piles.length;i++) {
            hours += piles[i] / x
            if(piles[i] % x > 0) {
                hours++
            }
        }
        return hours
    }
};

[jswxwxf]

875. 爱吃香蕉的珂珂 js 版，我用的两端都封闭的二分搜索

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function(piles, h) {
  let left = 1;
  let right = 1000000000;

  while (left <= right) {
    let mid = Math.floor(left + (right - left) / 2);
    if (f(piles, mid) === h) {
      // 搜索左侧边界，则需要收缩右侧边界
      right = mid - 1;
    } else if (f(piles, mid) < h) {
      // 需要让 f(x) 的返回值大一些
      right = mid - 1;
    } else if (f(piles, mid) > h) {
      // 需要让 f(x) 的返回值小一些
      left = mid + 1;
    }
  }
  return left;
}

// 定义：速度为 x 时，需要 f(x) 小时吃完所有香蕉
// f(x) 随着 x 的增加单调递减
function f(piles, x) {
  let hours = 0;
  for (let i = 0; i < piles.length; i++) {
    hours += Math.floor(piles[i] / x);
    if (piles[i] % x > 0) {
      hours++;
    }
  }
  return hours;
}

[Showcoding]

为什么我用两端闭会溢出？

[jswxwxf]

@lovelyJason f 函数你也要加上 Math.floor

[Alwin4Zhang]

爱吃香蕉的珂珂 python version

import math
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # 问题转化，搜索区间是[1,max_piles]
        # nums[mid]用于计算以当前的速度吃完香蕉的时间是多少小时
        # 需要求满足条件的最小speed，实际上就是左边界问题，因为不同的速度消耗时间是相同的
        def f(piles, speed):
            hours = 0
            for pile in piles:
                hours += math.ceil(pile / speed)
            return hours

        left, right = 1, max(piles) + 1
        while left < right:
            speed = left + (right - left) // 2
            hours = f(piles, speed)
            if hours > h:  # 要加快速度
                left = speed + 1
            elif hours < h:
                right = speed
            elif hours == h:
                right = speed
        return left

[Alwin4Zhang]

1011. 在D天内送达包裹的能力（中等）

# @lc code=start
class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def f(weights, capacity):
            cur = 0
            days = 0
            for i, weight in enumerate(weights):
                if cur + weight <= capacity:
                    cur += weight
                else:
                    cur = weight
                    days += 1
            return days + 1

        # 至少有一天承载了一天最重的包裹，所以最小值是max(weights)
        left, right = max(weights), sum(weights) + 1
        while left < right:
            capacity = left + (right - left) // 2
            need_days = f(weights, capacity)
            if need_days > days:  # 增大容量
                left = capacity + 1
            elif need_days < days:
                right = capacity
            elif need_days == days:
                right = capacity
        return left

[jyh-dev]

//java1011

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 0;
        for(int weight : weights){
            //最大运力保证刚好一次性运完所有包裹
            right += weight;
            //包裹不能拆开运所以至少保证载重能承载任意一个包裹；
            left = Math.max(left, weight);
        }
        while(left < right){
            int mid = left + (right - left) / 2;
            if(weightSum(weights, mid) > days){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    }
    public int weightSum(int[] weights, int speed){
        int sum = 0; 
        int res = 0;
        for(int weight : weights){
            sum += weight;
            if(sum > speed){
                res += 1;
                sum = weight;
            }
        }
        //加上最后一个不超载无法触发sum > speed 要补1，如果超载则最后一个要单独运输一次还要补1；
        return res + 1;
    }
}

[cheng-miao]

good

[yusongjohn]

第三题有一点点区别，那个单调函数用了贪心的思想。

单调函数的入参是maxSum，返回值表示最少分割次数。

对于一个给定的最大和 maxSum，最少能分割 minSplitTimes 次，那么 minSplitTimes ≤ m说 明当前的maxSum满足要求，那么继续缩小 maxSum ，看看有没最佳（小）的值。

[LebronHarden1]

这叫单调不增和单调不减,谢谢

[LebronHarden1]

感谢,模板真好用

[LebronHarden1]

class Solution {
    public int splitArray(int[] nums, int m) {
        //分析:求的是分组的数,和如何分组才能让某一组的组内元素之和是固定分组情况下所有情况的sum=min的min是多少
        //1.m分的越多:最大:每个元素为一组,那此时的maxSum就是nums中的最大元素的值
        //2.m分得越少:最小:整个nums为一组,此时的maxSum就是nums中所有元素之和
        //所以我们在研究分组的数量和最终的maxSum的关系
        if(nums==null||nums.length==0) return 0;
        int left=0;
        int right=0;
        for(int i=0;i<nums.length;i++){
            left=Math.max(left,nums[i]);
            right+=nums[i];
        }
        right++;//因为要左闭右开
        while(left<right){
            int mid=left+(right-left)/2;
            if(f2(nums,mid)<m){
                //分的组数太多了
                right=mid;
            }else if(f2(nums,mid)>m){
                //组数分的太少了
                left=mid+1;
            }else{
                //左边界
                right=mid;
            }
        }
        return left;
    }
    private int f2(int[] nums,int x){
        //让f(x)返回值是分组数,x为定死的maxSum
        int groups=1;
        int sum=0;
        for(int i=0;i<nums.length;i++){
            if(sum+nums[i]<=x){
                sum+=nums[i];
            }else{
                groups++;
                sum=nums[i];
            }
        }
        return groups;
    }
}

[Burkhardttt]

东哥，有个问题实在想请教，楼上看了一圈没有发现和我有一样问题的，就吃香蕉那题，我之前用Python写的，二分用的是双闭区间没有任何问题。今天用Java刷的时候也是同样的逻辑，但是用双闭区间就出问题了。

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 1;
        for (int pile : piles){
            right = Math.max(right, pile);
        }
        
        
        while (left <= right){
            int mid = left + (right - left) / 2;
            // System.out.print(left + ", " + right + ", " + mid);
            // System.out.print(", " + eatingTime(piles, mid) + ", ");
            if (eatingTime(piles, mid) > h){left = mid + 1;}
            else if (eatingTime(piles, mid) < h){right = mid - 1;}
            else if (eatingTime(piles, mid) == h){right = mid - 1;}
            // System.out.println(left + ", " + right + ", " + mid);
        }
        return left;
    }
    
    public int eatingTime(int[] piles, int k){
        int hours = 0;
        for (int i = 0; i < piles.length; i++){
            hours += piles[i] / k;
            if (piles[i] % k != 0){
                hours ++;
            }
        }
        return hours;
    }
}

倒在了测试用例piles = [805306368,805306368,805306368], h = 1000000000
然后我debug的时候发现是我代码里eatingTime(piles, mid)的返回值居然出现了负数，我查了一下应该是int类型越界了，需要long类型。之前Python代码通过是因为python的int范围更大。
但是改成左闭右开区间之后就没有这个问题了，下面的代码正确通过了。我真的在想是否二分采用左闭右开可以非常有效的规避掉这些情况，双闭区间逻辑上也没有任何问题，但是遇到这种情况感觉非常难第一时间想到出bug的原因。

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 1;
        for (int pile : piles){
            right = Math.max(right, pile);
        }
        right ++;
        
        
        while (left < right){
            int mid = left + (right - left) / 2;
            // System.out.print(left + ", " + right + ", " + mid);
            System.out.print(", " + eatingTime(piles, mid) + ", ");
            if (eatingTime(piles, mid) > h){left = mid + 1;}
            else if (eatingTime(piles, mid) < h){right = mid;}
            else if (eatingTime(piles, mid) == h){right = mid;}
            // System.out.println(left + ", " + right + ", " + mid);
        }
        return left;
    }
    
    public int eatingTime(int[] piles, int k){
        int hours = 0;
        for (int i = 0; i < piles.length; i++){
            hours += piles[i] / k;
            if (piles[i] % k != 0){
                hours ++;
            }
        }
        return hours;
    }
}

[hongyu-yan1998]

请问为什么左闭右开不会int越界呢？

[lauloong]

分享下自己的想法，如果有错误请指正。
首先，这个case仅当k = 1的时候，f()方法会int越界。
其次，左闭右开的时候，当出现满足的条件的时候，right = mid；当mid = 3时，是满足条件的，right = 3，下一次循环中mid = (1 + 3) / 2 = 2，此时k = 2 不会越界，也不会满足条件，left = 2 + 1 = right 结束循环
最后，左闭右闭的时候，当出现满足的条件的时候，right = mid - 1；当mid = 3时，是满足条件的，right = 2，下一次循环中mid = (1 + 2) / 2 = 1，此时k = 1 会越界，越界后满足条件，left = 1 = right - 1 继续循环，再循环一次后最终结果为left = 1, right = 0结束循环

[zhao-zihan]

今天遇到了跟楼上一模一样的问题，Java双闭区间同样的写法几天前还能过今天就不行了，但右开区间没问题，想了很久没明白为什么，持续关注这个问题，希望有大神指教

[huangzy1218]

class Solution {
    int f(int[] weights, int x) {
        int days = 0;
        for (int i = 0; i < weights.length; ) {
            int capacity = x;
            while (i < weights.length) {
                if (capacity < weights[i]) {
                    break;
                } else {
                    capacity -= weights[i];
                }
                i++;
            }
            days++;
        }
        return days;
    }

    public int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 0;
        for (int i = 0; i < weights.length; i++) {
            left = Math.max(left, weights[i]);
            right += weights[i];
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (f(weights, mid) > days) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

[ziranmyx]

判断搜索方向的函数也可以简单return一个boolean，也减少了前面提到溢出的问题：

·class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }
        int mid = 0;
        while(left <= right) {
            mid = left + (right - left)/2;
            if (canFinish(piles, h, mid)) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return left;
    }
    
    private boolean canFinish(int[] piles, int h, int speed) {
        for (int pile : piles) {
            h = h - (pile/speed) - (pile%speed > 0 ? 1 : 0); 
            if (h < 0) {
                return false;
            }
        }
        return true;
    }
}·

[Maxiah]

感觉我有点儿笨比，f(x)的函数变一下就写不出来了

[muum641651]

这几道题虽然写过，但是第一次用这种思路去看问题，感觉透彻了许多，感谢大佬！

[JiaRuiShao]

请教大家一下1011 运输包裹那道题的f(x)也就是给定mid的weightCapacity包裹运输时间的计算：我最开始写的是

private int calculateDays1(int[] weights, int weightCapacity) {
    int days = 0, weightSum = 0;
    for (int i = 0; i < weights.length;) {
        if (weightSum + weights[i] > weightCapacity) {
            days++;
            weightSum = 0;
            continue;
        }
        weightSum += weights[i++];
    }
    return days + weightSum > 0 ? 1 : 0;
}

但是怎么都通过不了，debug的时候才发现每次return的时候尽管weightSum > 0， 但是days也没有+1。return的时候只return了days。这里我把days在前一行update了之后再return就返回正常值了：

private int calculateDays2(int[] weights, int weightCapacity) {
    int days = 0, weightSum = 0;
    for (int i = 0; i < weights.length;) {
        if (weightSum + weights[i] > weightCapacity) {
            days++;
            weightSum = 0;
            continue;
        }
        weightSum += weights[i++];
    }
    // return days + weightSum > 0 ? 1 : 0; // didn't add 1 when weightSum > 0
    // in return
    days += weightSum > 0 ? 1 : 0;
    return days;
}

有人遇到过同样的问题或者是知道为什么会这样吗？

测试用例：

int[] weights = new int[]{1,2,3,4,5,6,7,8,9,10};
calculateDays1(weights, 32) = 1;
calculateDays2(weights, 32) = 2;

[Youareblind]

int f(int *weights, int weightsSize, int x)
{
    int day_count = 1, weight_count = 0;
    for(int i = 0; i < weightsSize; i++)
    {
        weight_count += weights[i];
        if(weight_count > x)
        {
            day_count++;
            weight_count = weights[i];
        }
    }
    return day_count;
}

[weixueman]

你最后不需要判断，直接day+1就行，因为你weightSum一定大于0

[Youareblind]

1011.的f函数这么写也许更容易理解一些

int f(int *weights, int weightsSize, int x)
{
    int day_count = 1, weight_count = 0;
    for(int i = 0; i < weightsSize; i++)
    {
        weight_count += weights[i];
        if(weight_count > x)
        {
            day_count++;
            weight_count = weights[i];
        }
    }
    return day_count;
}

[CharmSea]

东哥，能看一下吗，吃香蕉的那题，如果我用 闭区间 就没法通过，代码如下

    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 1000000000;
        int mid = 0;

        while (left <= right) {
            mid = left + (right - left) / 2;
            // 等于
            if (getHours(piles, mid) = h) {
                right = mid-1;
            }
            // 小于
            else if (getHours(piles, mid) < h) {
                right = mid - 1;
            }
            // 大于
            else if (getHours(piles, mid) > h) {
                left = mid + 1;
            }
        }
        return left;
    }

    private int getHours(int[] piles, int x) {
        int hours = 0;
        for (int i = 0; i < piles.length; i++) {
            hours += piles[i] / x;
            if (piles[i] % x > 0) {
                hours++;
            }
        }
        return hours;
    }

[huangzy1218]

class Solution {
    int f(int[] piles, int v) {
        int hours = 0;
        for (int pile : piles) {
            // 天坑
            hours += Math.floor(pile / v);
            if (pile % v > 0) {
                hours++;
            }
        }
        return hours;
    }

    public int minEatingSpeed(int[] piles, int h) {
        int left = 1, 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){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

[lhcezx]

复刷的时候发现了双闭区间的小问题，875. 爱吃香蕉的珂珂中122个用例中最后一个[805306368, 805306368, 805306368]无法通过，上面也有大佬提到了，原因是搜索到left = 1, right = 2时，此时mid = 1，调用getTime函数计算该速度下对应的时间，实际正确时间应该为2415919104但是由于C++中int类型会越界，所以导致该值变为-1879048192，从而导致二分搜索原本应该收缩左边界，变为收缩右边界从而导致出错，具体做法是只需要将辅助函数中统计时间变量和返回的变量改为unsigned int即可解决。下面贴一下自己的代码

class Solution {
public:
    unsigned int getTime(vector<int>& piles, unsigned int speed) {
        unsigned int time = 0;
        for (int i = 0; i < piles.size(); i++) {
            time += piles[i] % speed > 0 ? piles[i] / speed + 1 : piles[i] / speed;
        }
        return time;
    }

    int minEatingSpeed(vector<int>& piles, int h) {
        unsigned int left = 1, right = *max_element(piles.begin(), piles.end());
        while (left <= right) {
            unsigned int mid = left + (right - left) / 2;
            if (getTime(piles, mid) <= h) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

[zhoyifan]

这篇文章能用支付宝账号付款和绑定吗。我微信扫商店的码，登不进去。

[xz125]

不用记住，left 和 right 怎么更新的了，统一更新成mid的方法

package cn.msf.array;

/**
 * @author : msf
 * @date : 2022/12/21
 * 在D天内送达包裹的能力
 */
public class ShipWithinDays {
    public static void main(String[] args) {
        int[] weights = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int i = new ShipWithinDays().shipWithinDays(weights, 5);
        System.out.println(i);
    }

    public int shipWithinDays(int[] weights, int days) {
        int left = 0;
        int right = 0;
        for (int weight : weights) {
            left = Math.max(left, weight);
            right += weight;
        }
        left -= 1;
        // 保证size
        while (left + 1 != right) {
            int mid = left + ((right - left) >> 1);
            if (f(weights, mid) <= days) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private int f(int[] weights, int mid) {
        int days = 0;
        for (int i = 0; i < weights.length; ) {
            int cap = mid;
            while (i < weights.length) {
                if (cap < weights[i]) {
                    break;
                } else {
                    cap -= weights[i];
                    i++;
                }
            }
            days++;
        }
        return days;
    }
}

[xz125]

class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0;
        int right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        left--;
        while (left + 1 != right) {
            int mid = left + ((right - left) >> 1);
            if (split(nums, mid) <= k) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    /**
     *
     * @param nums 原始素组
     * @param mid 子数组各自和的最大值
     * @return 满足不超过 mid 的分割数
     */
    private int split(int[] nums, int mid) {
        int split = 1;
        // 当前区间和
        int curSum = 0;
        for (int num : nums) {
            // 尝试加上当前遍历的这个数，如果加上去超过了
            // 「子数组各自的和的最大值」，就不加这个数，另起炉灶
            if (curSum + num > mid) {
                curSum = 0;
                split++;
            }
            curSum += num;
        }
        return split;
    }
}

[RomeoFourier]

Java实现875. 爱吃香蕉的珂珂
解决用例{[805306368,805306368,805306368], 1000000000}的错误

错误原因出在博主原文那个f函数的返回值溢出了int的最大值，除了将f函数的返回值改成long以外，还可以给这个返回值设一个上限，上限为它所比较的那个数（h）的最大值1000000000。
具体来说就是，只要f函数的返回值在函数内部计算的过程中超过了1000000000就立即返回，因为这个返回值的作用只是和h去比大小，只要它超过了1000000000那么肯定也比h大。

    class Solution {
        public int minEatingSpeed(int[] piles, int h) {
            int left = 1, right = 1000000000 + 1;
            int mid, H;
            while (left <= right){
                mid = left + (right - left) / 2;
                H = f(piles, mid);
                if (H <= h) right = mid - 1;
                if (H > h) left = mid + 1;
            }
            return left;
        }
        public int f(int[] piles, int x){
            int hours = 0;
            for (int pile:piles) {
                hours += pile / x;
                if (pile % x > 0) hours++;
                if (hours > 1000000000) break;//防止返回值hours溢出
            }
            return hours;
        }
    }

[bruceeewong]

20230109 打卡，抽象成单调函数去应用二分搜索也太妙了

[krobz]

感谢大佬的文章，现在已经用地很熟练了。
有一个小疑问，本篇的lower boundary和upper boundary模板是不是只适用于target一定在数组里的情况，另外的情况可能要调整一下。
比如今天周赛里面的一个例子，nums=[1,3,6,8], target = 5。我用lower boundary模板得到的index是3，upper boundary模板得到的index是2。这种情况lower boundary的结果比upper boundary还大。这种情况下是不是没有lower boundary和upper boundary的概念。

[labuladong]

我感觉可能是你的代码写的有 bug，按照你说的 nums=[1,3,6,8], target = 5 的情况，left bound 应该是算出来是 2 才对，详情见 二分搜索模板

[krobz]

不好意思，我昨天打错了。left bound的结果是2，right bound的结果是1。循环终止的时候，两种模板的left好像都是2。

[CarlLy7]

打卡！！！过瘾

[c0sc0s]

var minEatingSpeed = function(piles, h) {
    const hit = k => {
        let t = 0;
        for(let i of piles) t+= Math.ceil(i/k);
        return t <= h;
    }

    let l = 0, r = Math.max(...piles) + 1;
    while(l != r - 1){
        const mid = Math.floor((l + r)/2);
        if(hit(mid)) r = mid;
        else l = mid;
    }
    return r ===  Math.max(...piles) + 1 ?  -1 : r;
};