引言

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

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

  • 二分查找适用于所有「在单调区间中搜索目标值」的问题
  • 二分查找的题目类型有:查找特定值、查找第一个大于等于特定值的元素(下界)、查找最后一个小于等于特定值的元素(上界)… 这些问题都可以通过套用同一个「查找下界」的模板来解决:
// 查找满足 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
}
个人笔记

这里 for 循环的 left <= right 换成 left < right 也可以。 后者可以理解为「左闭右开」区间。这道题里,left、right 既是要找下界的“值”,也是区间的“下标”。而「左闭右开」的写法里,下标是可以取到左右端点的,所以即使换成 left < right,left 也还是可以取到 sum。
<= 的写法相当于是包含了 < 的写法,最后会多一步计算。换成 < 后可以节省 4ms。

总结

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

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

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

本文发表在我的博客 https://imageslr.com/。我也会分享更多的题解,一起交流,共同进步!