【LeetCode】在实际问题中运用二分查找模板代码

引言

在上一篇文章中，我们介绍了「二分查找」的通用模板，并通过几个例题说明了如何套用这个模板。建议读者先阅读上一篇文章：一个模板通杀所有「二分查找」问题。

简要概括上一篇文章的主要内容：

• 二分查找适用于所有「在单调区间中搜索目标值」的问题
• 二分查找的题目类型有：查找特定值、查找第一个大于等于特定值的元素（下界）、查找最后一个小于等于特定值的元素（上界）… 这些问题都可以通过套用同一个「查找下界」的模板来解决：

// 查找满足 x ≥ target 的下界的下标
func LowerBound(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left) >> 1
        if nums[mid] >= target { // 这里的比较运算符与题目要求一致
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left // 返回下界的下标
}

本文将通过两个实际问题，深入讲解如何运用这个模板。

875. 爱吃香蕉的珂珂

这道题是 LeetCode 875 题：

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

首先分析题目：珂珂每小时只能选择某一堆香蕉，吃掉其中的 K 根；如果这一堆香蕉不够 K 根，那么珂珂吃完之后，也必须等到下一个小时才能继续吃另一堆。要求返回她可以在 H 小时内吃掉所有香蕉的最小速度 K。

显然，一种比较简单的方式是从 1 开始，依次递增 1，遍历所有可能的速度，返回第一个可以在 H 小时内吃掉所有香蕉的速度。

不过观察本题，我们容易发现：速度越快，吃掉所有香蕉的时间就越短。也就是说，搜索区间是单调递减的，因此可以使用二分查找。另外，本题要找的是可以在 H 小时内吃掉所有香蕉的最小速度，这实际上就是要查找下界。所以可以直接套用上面的模板代码：

func minEatingSpeed(piles []int, H int) int {
	// left, right，mid 的含义是「吃香蕉的速度」
	// 每小时最少吃一根香蕉，最多只能吃一堆香蕉，所以 left、right 的初值分别为 1、MaxOf(piles)
	left, right := 1, MaxOf(piles)
	for left <= right {
		mid := left + (right-left)>>1
		// 假设在 H 小时内「恰好」吃掉所有香蕉的速度为 targetSpeed，则判断条件可以写为：
		// if mid >= targetSpeed // 找下界，用 >=
		// 速度与时间成反比，因此判断条件等同于：
		if TotalTime(piles, mid) <= H {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}

func TotalTime(piles []int, k int) int {
	time := 0
	for _, v := range piles {
    		time += (v+k-1)/k // 向上取整
	}
	return time
}

func MaxOf(nums []int) int {
	m := -1 << 63
	for _, v := range nums {
		m = Max(m, v)
	}
	return m
}

func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

1011. 在 D 天内送达包裹的能力

这道题是 LeetCode 1011 题：

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

本题和 875 题很像，要返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力，这就相当于是在找下界，可以直接套用模板代码：

1. left、right 表示运载能力，其初值为 MaxOf(weights)、SumOf(weights)。原因：货物无法拆分为更小单位，故最小运载能力是每件货物的最大重量，最大运载能力是货物重量总和，即一批运走
2. 「运载能力」和「天数」成反比，因此判断条件写为 TotalTime(weights, mid) <= D，等同于 mid >= targetCapacity，其中 targetCapacity 是「恰好」在 D 天运送完所有包裹的运载能力

完整代码如下：

// 这里直接套用模板代码
func shipWithinDays(weights []int, D int) int {
	left, right := MaxOf(weights), SumOf(weights)
	for left <= right {
		mid := left + (right-left)>>1 // mid 的含义是「运载能力」
		if TotalTime(weights, mid) <= D {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}

func TotalTime(weights []int, capacity int) int {
	time := 1 // 初始化为第一天
	c := capacity
	i := 0
	for i < len(weights) {
		if c >= weights[i] {
			c -= weights[i] // 这一天还可以装
			i++
		} else {
			time++ // 这一天已经装满了，在下一天再装
			c = capacity
		}
	}
	return time
}

func MaxOf(nums []int) int {
	m := -1 << 63
	for _, v := range nums {
		m = Max(m, v)
	}
	return m
}

func SumOf(nums []int) int {
	m := 0
	for _, v := range nums {
		m += v
	}
	return m
}

func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

总结

本文通过两个实际问题，深入讲解了如何运用二分查找模板代码。我们发现，模板代码可以进一步优化为如下形式，从而适用于任何「查找下界」的问题：

func LowerBound(nums []int, target int) int {
    left, right := MIN, MAX // 最小值、最大值
    for left <= right {
        mid := left + (right-left) >> 1
        if IS_OK { // 这里的判断条件与题目要求一致
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
}

上面的代码中有三处变量 MIN、MAX、IS_OK，分别表示搜索区间的最小值、最大值、判断条件，根据题目要求填写：

• LeetCode 34 题：查找满足 x >=target 的第一个位置，故 MIN、MAX、IS_OK 分别为 0、n-1、nums[mid] >= target
  • 如果要查找满足 x >=target 的第一个位置，IS_OK 变为 nums[mid] > target
• LeetCode 875 题：查找可以在 H 小时内吃掉所有香蕉的最小速度，故 MIN、MAX、IS_OK 分别为 1、MaxOf(piles)、TotalTime(piles, mid) <= H
• LeetCode 1011 题：查找可以在 D 天内运损完所有货物的最小运载能力，故 MIN、MAX、IS_OK 分别为 MaxOf(weights)、SumOf(weights)、TotalTime(weights, mid) <= D

当题目要查找「最小值」、「第一个」时，就说明要查找「下界」，此时就可以使用这个模板。