Colin’s Blog

A C++ Programmer

二分问题的统一解决方案

思路来自 https://www.youtube.com/watch?v=QvcM99na30k。本文为学习记录+结合自己的思考修改后得出的框架。

引入

在算法题中有时候会遇到这种场景,对于一个问题,它的答案是一个整数且一定取在一个范围内,例如答案只可能是$[1, 10^9]$中的一个数字。且存在一个条件,使得对于任何小于答案的数字,这个条件都不成立;而对于任何大于等于答案的数字,这个条件都成立。那么这个时候就可以使用二分的方法来找到答案。

框架与求解

下面用严格的语言来表达这类问题(我称为二分问题):

存在一个函数 check , 它接受一个整数 i 作为输入, 且 check(i) 只可能等于 True or False .

并且,存在一个数 $k$ ,使得对于任何小于 $k$ 的整数 i ,都有 check(i)==False ,而对于任何大于等于$k$的整数 i ,有 check(i)==True . 我们现在有函数 check ,需要找到这个整数$k$. 且我们知道 $k$ 在 $[a,b]$ 区间内。

我们接下来提出一个框架来解决这个问题。

首先,我们从获取信息的角度思考这个问题。在我们去实际跑一次 check 函数之前,我们是没有获取任何信息的。这个时候我们可以认为所有的 $[a,b]$ 之间的整数都是未知状态。

而我们在运行了 check(i) 之后,由于问题的性质,我们获取到的信息不只是 check(i) 本身为真还是假。而是可以知道一个范围内的所有整数都满足或者不满足条件。

例如我运行了 check(i) ,得到 check(i)==False. 那么我就知道对于所有的 $[a,i]$ 闭区间内的整数,它们check的结果一定也都是 False .

而如果我运行了 check(i) ,得到 check(i)==True. 那么我就知道对于所有的 $[i,b]$ 闭区间内的整数,它们check的结果一定也都是 True .

定义一个闭区间 $[l,r]$ 为求解区间,使得它满足以下3条性质:

  1. $[l,r]$ 中全是我们未知它check的结果是True还是False的整数
  2. 对于任何大于 $r$ 的整数,check的结果一定是True
  3. 对于任何小于 $l$ 的整数,check的结果一定是False

接下来我们把求解区间初始化为 $[a,b]$. 因为一开始,$[a,b]$ 中全是我们未知的。

相当于我们定义了两个变量l,r, 且初始化它们为l<-a, r<-b.

然后定义变量mid, mid <- l + (r-l)/2 . mid也就是求解区间的中点。

然后计算check(mid).

如果check(mid)==True,说明 $[mid, r]$ 都是 True. 因此 $[mid, r]$ 从未知变为已知。需要让新的r变为 mid - 1. 也就是执行 r <- (mid - 1) .这个过程中维护了3条性质始终成立。

如果check(mid)==False,说明 $[l, mid]$ 都是 False. 因此 $[l, mid]$ 从未知变为已知。需要让新的l变为 mid + 1. 也就是执行 l <- (mid + 1) .这个过程中维护了3条性质始终成立。

然后重复执行 mid <- l + (r-l)/2 和上述操作。 直到 $r < l$ 为止。此时求解区间为空。也就是未知的区间为空。说明 $[a,b]$ 内的每一个整数的check情况已经全部已知。我们的目标就是把未知区间变为空。且保持3条性质均始终成立。

在未知区间为空之后,$r$ 一定等于 $l-1$. 此时,r就是最后一个False所在位置,而l就是第一个True所在位置。然后根据题目要求哪一个就返回哪一个就行。

举例子说明(可以先看这个部分)

例如对于一个check函数,假设我们把它应用在1,2,3,4,5,6,7,8,9上面,得到的结果分别是

$$ [F,F,F,F,T,T,T,T,T] $$

那么取 l <- 0, r <- 8. 计算得到 mid <- 4.

此时 check(mid) == check(4) == T. 说明 [4,8] 区间内的每一个整数check之后都是T. 因此它们从未知变成已知。 我们执行 mid <- (r - 1). 得到新的未知区间为 [l,r] == [0,3].

计算 mid <- (l+r)/2, 得到新的 mid == 1. 此时 check(mid) == F. 说明 [0,1] 区间均为F. 因此执行 mid <- (l + 1). 新的未知区间为 [l,r] == [2,3].

计算 mid <- (l+r)/2, 得到新的 mid == 2. 此时 check(mid) == F. 说明 [0,2] 区间均为F. 因此执行 mid <- (l + 1). 新的未知区间为 [l,r] == [3,3].

计算 mid <- (l+r)/2, 得到新的 mid == 3. 此时 check(mid) == F. 说明 [0,3] 区间均为F. 因此执行 mid <- (l + 1). 新的未知区间为 [l,r] == [4,3] == Empty.

计算结束。 此时 l == 4, r == 3. l就是第一个T所在的位置。 r就是最后一个F所在的位置。