我快要二分搜索PTSD了

最近遇到了好多看上去和二分搜索完全没关系的题目，一看提示竟然是二分搜索。我目前做过的这类题有

  • 278 找到第一个bad version

  • 1011 最少要多少天运完货

  • 1552 尽可能稀疏放球

  • 1283 找到最小的 \(n\) 使得数组每个元素除以 \(n\) 之后向上取整的累加和大于等于 \(t\)

  • 1631 最省力的爬山路径

痛定思痛，决定稍微研究一下这个问题，以后遇到类似的坑能及时发现。稍微研究过后发现，背后的本质是归约（所以标题其实不太贴切，二分只是实现两种表述之间转换的overhead最小、最高效的方法），竟然在上学期的算法课里重点讲过，之前自己总结NP和归约的文章里也提过，没几天居然就忘了，真是学艺不精啊……

字面意思的二分搜索

先来回顾一下普通的二分搜索的目的是啥。简单来说是给一个排好序的array，这里就假设是从小到大排好序的，比如

1, 2, 3, 3, 3, 4, 5

现在要插入一个新的数字，假设就是3，要把这个3插入到某个位置之后，原array仍然保持有序。二分搜索就是寻找这样一个位置、使得元素 插入 到这个位置之后、array仍然保持有序的过程。

在上面这个例子里面，3可以插入的位置有4个

1, 2, 3, 3, 3, 4, 5
    ^  ^  ^  ^

在这几个位置插入3，都可以使得array保持有序。

注意二分搜索并不一定是找到某个元素的位置，因为array里可能根本不存在这个元素。

比如如果换成2.5，原array根本就不存在2.5，可插入的位置只有

1, 2, 3, 3, 3, 4, 5
    ^

既然有时候可插入的位置不止一个，那么我们最关心哪个位置呢？通常最关心最靠左和最靠右的两个位置。最左和最右在代码里的差别很小，区别在于相等的时候收紧左边界还是收紧右边界。

不管有的没的了，先来看怎么找到最左插入位置。首先我们有两个指针 left, right 表示当前我们的搜索范围是 array[left..right] 。注意左闭右开。也就是说我们现在想在 array[left..right] 里找一个最靠左的位置插入数字 target 。

[1, 2, 3, 3, 3, 4, 5)
l                   r
0                   7

现在取 left, right 的平均数 \(\left\lfloor {l + r \over 2} \right\rfloor\) 记为 middle 。

这样一来，我们把 array[left..right] 拆成了 array[left..middle], array[middle..middle + 1], array[middle + 1..right] 三部分。

[1, 2, 3)[3)[3, 4, 5)
l       m  m+1      r
0       3  4        7

并且因为有序的性质， array[left..middle] 里任意一个元素都小于等于 array[middle] ， array[middle + 1..right] 里任意一个元素都大于等于 array[middle] 。

所以如果 target 小于 array[middle] 的话，把它插入 array[left..middle] 里的某个位置才能维持有序；如果 target 大于 array[middle] 的话，把它插入 array[middle + 1..right] 里的某个位置才能维持有序。

比如现在要插入2.5，它比当前 array[middle] == 3 要小，所以目前来说，它只可能被插入到这4个位置

                    2.5?
v v  v  v
[1, 2, 3)[3)[3, 4, 5)
l       m  m+1      r
0       3  4        7

然后继续锁定左半部分搜索就可以了，右边比它大的数都不用管了，因为根本不可能。这下子少了一半的搜索范围，非常爽。

备注

有没有一点递归的感觉了？当前层只要考虑继续搜索左边还是右边就可以了，确定好之后交给下层处理。

如果是插入5，它比当前 array[middle] == 3 要大，目前来说，它只可能被插入到这4个位置

5?
           v  v  v  v
[1, 2, 3)[3)[3, 4, 5)
l       m  m+1      r
0       3  4        7

同样整个左半边直接不用管了。

所谓二分，分的是搜索范围。每次搜索范围减半，才使得复杂度变成 \(O(\ln n)\) 。

以2.5为例，整个搜索过程是这样的

  1. 和 array[3] == 3 比较，发现比3小，所以搜索范围坍塌到左半边

                        2.5?
v v  v  v
[1, 2, 3)[3)[3, 4, 5)
l       m  m+1      r
0       3  4        7

  2. 和 array[1] == 2 比较，发现比2大，搜索范围坍缩到右半边

                        2.5?
     v  v
[1)[2)[3) 3, 3, 4, 5
l m     r
0 1  2  3

  3. 和 array[2] == 3 比较，发现比3小，搜索范围坍缩到左半边

                        2.5?
    v
1, 2[)3[)3, 3, 4, 5
    [   )
    l   r
    m
    2   3

  4. 搜索范围现在是 array[2..2] ，这已经是个空区间了，所以结果是2

再来说最左和最右的事情。比如现在要插入3，发现竟然和 array[middle] == 3 相等，怎么办？这样不是没办法确定继续搜左边还是右边了吗？很简单，如果想要找最靠左的插入位置，在 target == array[middle] 的时候，当做 target < array[middle] 一样、继续往左半边搜索就可以了；同样如果想要找最靠右的插入位置，往右半边搜索就可以了。

以插入3为例，如果要找最靠左插入位置，过程是这样的：

  1. 和 array[3] == 3 比较，发现和3一样大，搜索范围坍塌到左半边

                        3?
v v  v  v
[1, 2, 3)[3)[3, 4, 5)
l       m  m+1      r
0       3  4        7

  2. 和 array[1] == 2 比较，发现比2大，搜索范围坍缩到右半边

                        3?
     v  v
[1)[2)[3) 3, 3, 4, 5
l m     r
0 1  2  3

  3. 和 array[2] == 3 比较，发现和3一样大，搜索范围坍缩到左半边

                        2.5?
    v
1, 2[)3[)3, 3, 4, 5
    [   )
    l   r
    m
    2   3

  4. 搜索范围现在是 array[2..2] ，这已经是个空区间了，所以结果是2

如果要找最右插入位置，过程是这样的

  1. 和 array[3] == 3 比较，发现和3一样大，所以搜索范围坍塌到右半边

                        3?
           v  v  v  v
[1, 2, 3)[3)[3, 4, 5)
l       m  m+1      r
0       3  4        7

  2. 和 array[1] == 4 比较，发现比4小，搜索范围坍缩到左半边

                       3?
          v  v
1, 2, 3, 3 [3)[4)[5)
          l  m     r
          4  5  6  7

  3. 和 array[4] == 3 比较，发现和3一样大，搜索范围坍缩到右半边

                        3?
             v
1, 2, 3, 3[)3[)4, 5
          [  )
          l  r
          m
          4  5

  4. 搜索范围现在是 array[5..5] ，这已经是个空区间了，所以结果是5

代码怎么写呢？有递归式和迭代式两种写法。

先来说极为先进的递归式写法，配合Rust非常优雅，几乎就是刚才文字分析的直接翻译

fn binary_search_left(array: &[i32], target: i32) -> usize {
    let middle = (0 + array.len()) / 2;

    match array.get(middle) {
        Some(v) => match target.cmp(v) {
            Ordering::Equal => binary_search_left(&array[..middle], target), // 相等的时候和小于处理方法相同，搜索范围缩小到左半边
            Ordering::Less => binary_search_left(&array[..middle], target), // 小于的时候，搜索范围缩小到左半边
            Ordering::Greater => {
                middle + 1 + binary_search_left(&array[middle + 1..], target)
            } // 大于的时候，搜索范围缩小到右半边。注意要加middle + 1偏移
        },
        _ => 0, // 空区间
    }
}

迭代法也很简单，把缩小范围这个操作从递归里面的取slice，变成动 left, right 指针

fn binary_search_left(array: &[i32], target: i32) -> usize {
    let mut left = 0;
    let mut right = array.len();

    while left < right {
        let middle = (left + right) / 2;
        if target > array[middle] {
            left = middle + 1; // 下一次搜索array[middle + 1..right]
        } else if target < array[middle] {
            right = middle; // 下一次搜索array[left..middle]
        } else {
            right = middle; // 下一次搜索array[left..middle]
        }
    }

    return left;
}

看到这里可以做704了。

求极值表述和判定表述

重头戏来了，除了704这种直勾勾的叫你写二分，其他的题目都会把二分隐藏起来。拙劣一点的隐藏方法像是278，稍微分析下，把问题转化成单调递增数列就可以解决。

278题目给了个非常有意思的背景：有版本号从1到 \(n\) ，某个版本不小心写了个bug，导致这个版本及后面的版本都存在bug，要找到这个bug第一次出现的版本号。

抽象一下

给个 \(f\) 函数，定义域是 \([1, 2, 3, ..., n]\) ，存在一个 \(j \in [1, n]\) ，有

\[\forall i \in [1, j): \quad f(i) = 0\]

和

\[\forall i \in [j, n]: \quad f(i) = 1\]

找到这个 \(j\) 。

把 \(f\) 写成数列的样子大概是这样的

\[\begin{split}\begin{matrix} 1 & 2 & 3 & \cdots & j - 1 & j & j + 1 & \cdots & n - 1 & n & \quad i \\ 0 & 0 & 0 & \cdots & 0 & 1 & 1 & \cdots & 1 & 1 & \quad f(i) \end{matrix}\end{split}\]

\(f\) 的取值长得像个 [0, 0, ..., 0, 1, 1, ..., 1] 这样的array，这个array虽然都是0和1，可是也是单调递增的，所以一样可以用二分。问题马上转化成了“如果插入1，最靠左的插入位置是哪里”。

class Solution:
    def firstBadVersion(self, n: int) -> int:
        target = True
        left = 1
        right = n + 1

        while left < right:
            middle = (left + right) // 2
            test = isBadVersion(middle) # 如果在array里二分，这里是array[middle]，这里只不过改成了f(middle)
            if target < test:
                right = middle
            elif target > test:
                left = middle + 1
            else:
                right = middle

        return left

对于最前面列出的其他问题就没那么容易看出来。1011、1552、1631等题目的题面是找某个满足条件的极值。

比如1011是关于运货的题目

一批货要按顺序依次发出，你只有一艘船，一天只能来回一趟，要在 \(d\) 天内运完，那么这艘船的载重量最小必须是多少，才能让所有的货物在 \(d\) 天内运完？

比如这批货的重量是 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ，要在5天内运完，一艘载重量是15的船是足够的

  1. 第1天运 1, 2, 3, 4, 5

  2. 第2天运 6, 7

  3. 第3天运 8

  4. 第4天运 9

  5. 第5天运 10

但是一艘载重量是14的船就不行

  1. 第1天运 1, 2, 3, 4

  2. 第2天运 5, 6

  3. 第3天运 7

  4. 第4天运 8

  5. 第5天运 9

  6. 第6天运 10

要6天。

比如1283是找最小除数的问题

给个array，找到一个数字 \(k\) ，使得array里面每个数字 \(a_i\) 除以 \(k\) 并且向上取整之后的累加和 \(\sum_{a_i} \lceil a_i / k \rceil\) 小于等于 \(t\) 。

比如假设array是 1, 2, 3, 4 ， \(t = 5\) ，如果所有的数字都先除以3、向上取整

1, 2, 3, 4
1, 1, 1, 2

累加和是5。

如果所有数字都先除以2、向上取整

1, 2, 3, 4
1, 1, 2, 2

累加和是6。

用通常的方法一点办法都没有（也可能是我太菜），然而观察这些问题之后可以找到两个重要性质

  • 验证“某个具体的值能不能满足要求”很容易写出来

    比如1011运货的题目，如果直接告诉你货船的载重量是多少，很容易算出最少需要几天才能运完，每天尽量多装货、尽量装满货船肯定是最省时间的。

    比如1283，如果直接给 \(k\) ，遍历array一遍，算出 \(\sum_{a_i} \lceil a_i / k \rceil\) 是多少，和 \(t\) 比较一下，看看累加和是不是小于等于 \(t\) 就行了。

    最丧心病狂的是1631，要用BFS才能验证花费那么多力气能不能到山顶。但其实也还好，能写。

  • 一旦找到了某个值 \(k\) 满足要求，那么 \(k + 1, k + 2, ...\) 只要是大于等于 \(k\) 的值都满足要求

    比如1011，如果载重量是5的货船能在10天内运完，更大的、载货量是6的货船也一定至少能在10天内运完。没道理载货量更大结果花费时间更长。

    比如1283，如果 \(k = 3\) 能让累加和等于5，那么 \(k = 4\) 的时候，每个数字被除以了更大的数，整个累加和肯定小于等于 \(k = 3\) 的时候的累加和。

    比如1631，如果找到了一条花费6能量的上山路径，那么最多花费7能量也一定能上山，因为你走那条花费6能量的上山路就好了，走完还有1能量结余。

换言之，这几个问题的题面虽然是找满足条件的最小值，但是如果我们不停地询问“50行不行”、“25行不行”、“17行不行”，最终竟然也是可以间接问出最小值的！

举个例子，有个资本家在上海有5套房子，你想知道他在上海有多少套房子，但是他不想直接告诉你他在上海有5套房子，怕你直接喊“打倒资本家”，他说“当你猜的数额大于等于我实际拥有的房子的数量时，我会点头，否则我会摇头”。

这个问题里面，你猜了一个 \(k\) 并且资本家点头可以看成是函数 \(f(k) = 1\) ，所以满足第一个性质；同时，一旦你猜了某个 \(k\) 并且资本家点头了，你可以百分百确定，当你猜 \(k + 1\) 的时候，资本家还是会点头，所以第二个性质也满足。

这时候你就可以这么猜了。首先你调查了一番全上海总共有多少套房子，假设是 \(100\) 吧，这个资本家可能超级有钱，上海所有的房子都是他的；资本家也有可能在上海一套房子都没有，他可能在北京有房子。

所以一开始你认为资本家的房产数量是 \([0, 100]\) 区间里面的某个数字。于是你

  1. 猜了 \(\lfloor (0 + 100) / 2 \rfloor = 50\)，资本家点头了，于是你确定资本家的房产数量是 \([0, 500]\) 里的某个数字

  2. 猜了 \(\lfloor (0 + 50) / 2 \rfloor = 25\) ，资本家也点头了，于是你进一步缩小范围到 \([0, 250]\)

  3. 猜了 \(\lfloor (0 + 25) / 2 \rfloor = 17\) ，资本家点头了，于是缩小范围到 \([0, 17]\)

  4. 猜了 \(\lfloor (0 + 17) / 2 \rfloor = 8\) ，资本家点头了，范围缩小到 \([0, 8]\)

  5. 猜了 \(\lfloor (0 + 8) / 2 \rfloor = 4\) ，资本家摇头了！范围缩小到 \([5, 8]\)

  6. 猜了 \(\lfloor (5 + 8) / 2 \rfloor = 6\) ，资本家点头了，范围缩小到 \([5, 6]\)

  7. 猜了 \(\lfloor (5 + 6) / 2 \rfloor = 5\) ，资本家点头了，范围缩小到 \([5, 5]\) ，此时区间里只有一个数字了，所以资本家在上海有5套房子

这个例子里，虽然我们没法直接从资本家那里知道他到底有多少套房子，但是我们可以通过问他这种是或者否的判定问题，来间接得到想要的答案。或者说，如果能解决判定问题，就能解决找极值的问题。

我们问了多少次判定问题呢？刚才的范围是 \([0, 100]\) ，只问了7次就得到了答案，虽然不如只问1次来的爽快，不过也非常节能了。你可以试试，范围是 \([0, 1000]\) 的时候，只需要问10次；范围是 \([0, 10000]\) 的时候，只要问13次……范围是 \([0, 10^9]\) 的时候，也只需要问30次。太节能了。

如果范围是 \([0, n]\) ，那么需要问 \(O(\ln n)\) 次 [1] 判定问题。如果判定问题本身的复杂度是 \(p(n)\) ， \(p(n)\) 可能是 \(O(2^n), O(n), O(n!)\) 什么都有可能。那么通过问判定问题来解决原问题的总的复杂度是 \(p(n) \ln n\) ，比 \(p(n)\) 慢一点点。

根据定义，如果某个算法关于输入规模 [2] 的复杂度上界是多项式阶，即使它是 \(O(n^{99999})\) ，也认为是 能够高效解决的 。因为对于任意 \(n > 1\) ，都有 \(\ln n < n\) ，所以 \(p(n) \ln n < p(n) \cdot n\) 。如果 \(p(n)\) 上界是多项式阶的，那么 \(p(n) \ln n\) 的上界仍然是多项式阶的。

比如假设 \(p(n) = n^2 \in O(n^2)\) ，那么 \(p(n) \ln n = n^2 \ln n < n^2 \cdot n = n^3\) ，所以 \(p(n) \ln n \in O(n^3)\) 。

因此我更愿意认为，找极值和判定完全是同一个问题的两种不同的表述、两种不同的表象。两个表象之间用二分联系在一起。

备注

当然你也可以选择不用二分，暴力搜索 \([0, n]\) 完全可以。只不过二分是沟通两个表象overhead最小的方式。在理论上、从复杂度上界的角度看，大家都是高效的，没有谁比谁更高贵。在实际应用里， \(O(n^2 \ln n)\) 和 \(O(n^3)\) 差别还是挺大的……我感觉 \(O(n^2 \ln n)\) 和 \(O(n^2)\) 几乎没有差别。

所以如果能解决判定问题、并且还能高效解决判定问题的话，那么不仅能解决极值问题、还能高效解决极值问题。判定问题的代码又只是验证，通常很好写，一来一去简直赚大了，建议全宇宙推广。

比如1011的代码

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def feasible(capacity: int) -> bool:
            count = 0 # 运了多少天了
            loaded = 0 # 现在即将出发的货船上已经装了多少货

            for v in weights:
                if loaded + v > capacity: # 如果现在这艘船装不下这个货物
                    count += 1 # 那这个箱子只能赶明天的趟了
                    loaded = v
                else: # 还好能装下
                    loaded += v

            if loaded != 0: # 最后一批货也得运一天
                count += 1

            return count <= D # 能不能在D天内运完呢？

        target = True
        left = max(weights)
        right = sum(weights) + 1

        while left < right:
            middle = (left + right) // 2
            test = feasible(middle)
            if target < test:
                right = middle
            elif target > test:
                left = middle + 1
            else:
                right = middle

        return left

比如1283的代码

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def feasible(divisor: int) -> bool:
            return sum(math.ceil(v / divisor) for v in nums) <= threshold # 累加和能不能小于等于threshold呢？

        target = True
        left = 1
        right = 2 * max(nums) + 1

        while left < right:
            middle = (left + right) // 2
            test = feasible(middle)
            if target < test:
                right = middle
            elif target > test:
                left = middle + 1
            else:
                right = middle

        return left

极其相似，只是变了一下判定函数 \(f\) 的定义、初始 left, right 而已。判定函数写起来毫无技术含量。

left 一般是判定函数 \(f\) 定义域的最小值， right 是 \(f\) 定义域的最大值加上1。加上1是为了和二分一开始的定义“找插入位置”和谐，例如 \(f\) 在定义域上所有的输出都是0，没有1，这时候二分会得到 \(n + 1\) ，表示如果要插入1，应该插入到 \(n + 1\) 的位置上。

2020/11/9

Canon & Baroque