分享丨【算法题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小）

灵茶山艾府

595514

发布于未知归属地

数组数学二分查找 C++Java 周赛数据结构数据结构与算法双周赛技巧力扣竞赛学习分享

二分题单二分查找二分算法二分入门二分题目力扣二分 leetcode 二分灵茶山艾府灵神灵神题单

图：闭区间二分循环结束时的左右指针位置（查找第一个 $8$ ）

刷题建议：初次刷题可以只刷难度低于 $1700$ 分的题目。难度更高的题目常常结合其他算法（数据结构、图论等）。

一、二分查找

讲解：二分查找红蓝染色法【基础算法精讲 04】

设 $nums$ 为递增（非递减）数组，长为 $n$ 。

二分查找常用转化表：

需求	写法	如果不存在
$\geq x$ 的第一个整数的下标	$lowerBound (nums, x)$	结果为 $n$
$> x$ 的第一个整数的下标	$lowerBound (nums, x + 1)$	结果为 $n$
$< x$ 的最后一个整数的下标	$lowerBound (nums, x) - 1$	结果为 $- 1$
$\leq x$ 的最后一个整数的下标	$lowerBound (nums, x + 1) - 1$	结果为 $- 1$

需求	写法
$< x$ 的整数个数	$lowerBound (nums, x)$
$\leq x$ 的整数个数	$lowerBound (nums, x + 1)$
$\geq x$ 的整数个数	$n - lowerBound (nums, x)$
$> x$ 的整数个数	$n - lowerBound (nums, x + 1)$

注意 $< x$ 和 $\geq x$ 互为补集，元素个数之和为 $n$ 。 $\leq x$ 和 $> x$ 同理。

§1.1 基础

§1.2 进阶

部分题目需要先排序，然后在有序数组上二分查找。

思维扩展：

74. 搜索二维矩阵
1287. 有序数组中出现次数超过 25% 的元素做到 $O (lo g n)$
2476. 二叉搜索树最近节点查询 1597
2070. 每一个查询的最大美丽值 1724
4012. 统计每个班次结束后的未完成任务数 1736
1150. 检查一个数是否在数组中占绝大多数（会员题）

二、二分答案

“花费一个 $lo g$ 的时间，增加了一个条件。” —— 二分答案

§2.1 求最小

题目求什么，就二分什么。

答疑

问：如何把二分答案与数组上的二分查找联系起来？

答：假设答案在区间 $[2, 5]$ 中，我们相当于在一个虚拟数组 $[check (2), check (3), check (4), check (5)]$ 中二分找第一个（或者最后一个）值为 $true$ 的 $check (x)$ 。这同样可以用红蓝染色法思考。

问：有些题目，明明 $m$ 可以是答案，但却不在初始二分区间中。比如闭区间二分初始化 $right = m - 1$ （或者开区间 $right = m$ ），这不会算错吗？

答：不会算错。注意「答案所在区间」和「二分区间」是两个概念。想一想，如果二分的 $while$ 循环每次更新的都是 $left$ ，那么最终答案是什么？正好就是 $m$ 。一般地，如果一开始就能确定 $m$ 一定可以满足题目要求，那么 $m$ 是不需要在二分区间中的。换句话说，二分区间是「尚未确定是否满足题目要求」的数的范围。那些在区间外面的数，都是已确定的满足（不满足）题目要求的数。

问：什么是循环不变量？

答：想一想，对于求最小的题目，开区间二分的写法，为什么最终返回的是 $right$ ，而不是别的数？在初始化（循环之前）、循环中、循环结束后，都时时刻刻保证 check(right) == true 和 check(left) == false，这就叫循环不变量。根据循环不变量，循环结束时 $left + 1 = right$ ，那么 $right$ 就是最小的满足要求的数（因为再 $- 1$ 就不满足要求了），所以答案是 $right$ 。

注：部分题目可以优化二分边界，减少二分次数，从而减少代码运行时间。对于初次接触二分答案的同学，无需强求自己写出最优的代码，设定一个比较大的二分上界也是可以的。

开区间二分模板（求最小）：

Python3

Java

C++

class Solution:
    # 计算满足 check(x) == True 的最小整数 x
    def binarySearchMin(self, nums: List[int]) -> int:
        # 二分猜答案：判断 mid 是否满足题目要求
        def check(mid: int) -> bool:
            # TODO

        left =   # 循环不变量：check(left) 恒为 False
        right =   # 循环不变量：check(right) 恒为 True
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            if check(mid):  # 说明 check(>= mid 的数) 均为 True
                right = mid  # 接下来在 (left, mid) 中二分答案
            else:  # 说明 check(<= mid 的数) 均为 False
                left = mid  # 接下来在 (mid, right) 中二分答案
        # 循环结束后 left+1 = right
        # 此时 check(left) == False 而 check(left+1) == check(right) == True
        # 所以 right 就是最小的满足 check 的值
        return right

1283. 使结果不超过阈值的最小除数 1542
2187. 完成旅途的最少时间 1641
1011. 在 D 天内送达包裹的能力 1725
875. 爱吃香蕉的珂珂 1766
4008. 击败所有怪物的最小初始强度 1776
3296. 移山所需的最少秒数注：由于有其他做法，难度分会低一些，二分做法估计 1850
3639. 变为活跃状态的最小时间 1853
475. 供暖器
2594. 修车的最少时间 1915
1482. 制作 m 束花所需的最少天数 1946
3924. 有限重边的最小阈值路径 2080
3048. 标记所有下标的最早秒数 I 2263
3807. 修复边以遍历图的最小成本（会员题）
2604. 吃掉所有谷子的最短时间（会员题）
2702. 使数字变为非正数的最小操作次数（会员题）

思维扩展：

§2.2 求最大

一图掌握二分答案！四种写法！

请注意「求最小」和「求最大」在二分写法上的区别。

「求最小」和二分查找求「排序数组中某元素的第一个位置」是类似的，按照红蓝染色法，左边是不满足要求的（红色），右边则是满足要求的（蓝色）。

「求最大」的题目则相反，左边是满足要求的（蓝色），右边是不满足要求的（红色）。这会导致二分写法和上面的「求最小」有一些区别。

以开区间二分为例：

求最小：check(mid) == true 时更新 right = mid，反之更新 left = mid，最后返回 right。
求最大：check(mid) == true 时更新 left = mid，反之更新 right = mid，最后返回 left。

对于开区间写法，简单来说 check(mid) == true 时更新的是谁，最后就返回谁。相比其他二分写法，开区间写法不需要思考加一减一等细节，推荐使用开区间写二分。

开区间二分模板（求最大）：

Python3

Java

C++

class Solution:
    # 计算满足 check(x) == True 的最大整数 x
    def binarySearchMax(self, nums: List[int]) -> int:
        # 二分猜答案：判断 mid 是否满足题目要求
        def check(mid: int) -> bool:
            # TODO

        left =   # 循环不变量：check(left) 恒为 True
        right =   # 循环不变量：check(right) 恒为 False
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid  # 注意这里更新的是 left，和上面的模板反过来
            else:
                right = mid
        # 循环结束后 left+1 = right
        # 此时 check(left) == True 而 check(left+1) == check(right) == False
        # 所以 left 就是最大的满足 check 的值
        return left  # check 更新的是谁，最终就返回谁