二分搜索的应用 | LianoのBlog

AI summary

type

status

date

slug

summary

原始的二分搜索代码

在具体的算法问题中，常用到的是「搜索左侧边界」和「搜索右侧边界」这两种场景，很少有让你单独「搜索一个元素」。

「搜索左侧边界」的二分搜索算法的具体代码实现如下：

「搜索右侧边界」的二分搜索算法的具体代码实现如下：

注意，本文我写的都是左闭右开的二分搜索写法，如果你习惯两端都闭的写法，可以参考前文自行修改。

二分搜索问题的泛化

什么问题可以运用二分搜索算法技巧？

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

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

1、f(x) 必须是在 x 上的单调函数（单调增单调减都可以）。

2、题目是让你计算满足约束条件 f(x) == target 时的 x 的值。

上述规则听起来有点抽象，来举个具体的例子：

给你一个升序排列的有序数组 nums 以及一个目标元素 target，请你计算 target 在数组中的索引位置，如果有多个目标元素，返回最小的索引。

这就是「搜索左侧边界」这个基本题型，解法代码之前都写了，但这里面 x, f(x), target 分别是什么呢？

我们可以把数组中元素的索引认为是自变量 x，函数关系 f(x) 就可以这样设定：

其实这个函数 f 就是在访问数组 nums，因为题目给我们的数组 nums 是升序排列的，所以函数 f(x) 就是在 x 上单调递增的函数。

最后，题目让我们求什么来着？是不是让我们计算元素 target 的最左侧索引？

是不是就相当于在问我们「满足 f(x) == target 的 x 的最小值是多少」？

可以画图如下：

如果遇到一个算法问题，能够把它抽象成这幅图，就可以对它运用二分搜索算法。

运用二分搜索的套路框架

想要运用二分搜索解决具体的算法问题，可以从以下代码框架着手思考：

具体来说，想要用二分搜索算法解决问题，分为以下几步：

确定 x, f(x), target 分别是什么，并写出函数 f 的代码。

找到 x 的取值范围作为二分搜索的搜索区间，初始化 left 和 right 变量。

根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。

例题

纸上得来终觉浅，多说无益，直接看题。

875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

那么，对于这道题，如何运用刚才总结的套路，写出二分搜索解法代码？

按步骤思考即可：

1、确定 x, f(x), target 分别是什么，并写出函数 f 的代码。

自变量 x 是什么呢？回忆之前的函数图像，二分搜索的本质就是在搜索自变量。

所以，题目让求什么，就把什么设为自变量，珂珂吃香蕉的速度就是自变量 x。

那么，在 x 上单调的函数关系 f(x) 是什么？

显然，吃香蕉的速度越快，吃完所有香蕉堆所需的时间就越少，速度和时间就是一个单调函数关系。

所以，f(x) 函数就可以这样定义：

若吃香蕉的速度为 x 根/小时，则需要 f(x) 小时吃完所有香蕉。

代码实现如下：

2、找到 x 的取值范围作为二分搜索的搜索区间，初始化 left 和 right 变量。

珂珂吃香蕉的速度最小是多少？最大是多少？

显然，最小速度应该是 1，最大速度是 piles 数组中元素的最大值，因为每小时最多吃一堆香蕉，胃口再大也白搭嘛。

这里可以有两种选择，要么你用一个 for 循环去遍历 piles 数组，计算最大值，要么你看题目给的约束，piles 中的元素取值范围是多少，然后给 right 初始化一个取值范围之外的值。

我选择第二种，题目说了 1 <= piles[i] <= 10^9，那么我就可以确定二分搜索的区间边界 left, right = 1, 10^9+1。因为我们二分搜索是对数级别的复杂度，所以 right 就算是个很大的值，算法的效率依然很高。

3、根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。

现在我们确定了自变量 x 是吃香蕉的速度，f(x) 是单调递减的函数，target 就是吃香蕉的时间限制 H，题目要我们计算最小速度，也就是 x 要尽可能小，所以选择左边界。

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

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

和上一题差不多。x 是船的运载能力，f(x) 是天数，target 是最小的 x。

好好品一品。

410. 分割数组的最大值

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
设计一个算法使得这 k 个子数组各自和的最大值最小。

传说中的困难题😮

这个题目有点类似前文一道经典动态规划题目 887. 鸡蛋掉落，题目比较绕，又是最大值又是最小值的。

简单说，给你输入一个数组 nums 和数字 m，你要把 nums 分割成 m 个子数组。

肯定有不止一种分割方法，每种分割方法都会把 nums 分成 m 个子数组，这 m 个子数组中肯定有一个和最大的子数组对吧。

我们想要找一个分割方法，该方法分割出的最大子数组和是所有方法中最大子数组和最小的。

我滴妈呀，这个题目看了就觉得难的不行，完全没思路，这题怎么运用我们之前说套路，转化成二分搜索呢？

其实，这道题和上面讲的运输问题是一模一样的，不相信的话我给你改写一下题目：

你只有一艘货船，现在有若干货物，每个货物的重量是 nums[i]，现在你需要在 m 天内将这些货物运走，请问你的货船的最小载重是多少？

这不就是刚才我们解决的力扣第 1011 题「在 D 天内送达包裹的能力」吗？

货船每天运走的货物就是 nums 的一个子数组；在 m 天内运完就是将 nums 划分成 m 个子数组；让货船的载重尽可能小，就是让所有子数组中最大的那个子数组元素之和尽可能小。

有人要问了，这里不是固定要 m 天吗，而上一题是最多 m 天，其实是一样的，少装点摸鱼一天不就得了，不会影响载重（子数组和的最大值）。

所以这道题的解法直接复制粘贴运输问题的解法代码即可：

本文就到这里，总结来说，如果发现题目中存在单调关系，就可以尝试使用二分搜索的思路来解决。搞清楚单调性和二分搜索的种类，通过分析和画图，就能够写出最终的代码。