二分问题的统一解决方案
思路来自 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条性质:
- $[l,r]$ 中全是我们未知它check的结果是True还是False的整数
- 对于任何大于 $r$ 的整数，check的结果一定是
True - 对于任何小于 $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所在的位置。