The secret of being a bore is to tell everything

0%

二分法杂谈

学算法一年了,做了很多题,但是对于二分法这块一直不是很明白。 有时候遇到二分答案的问题经常要调好长时间才能写对,有些时候就是看别人二分是怎么写的就照抄,但是并不清楚为什么这么写是对的。今天总结了一下二分法的几种情况以及它们的思路。

二分的写法

网上的二分法普遍有两种写法,一种是左闭右开[l, r)的写法,一种是左闭右闭[l, r]的写法。左闭右开写法的优点是上下界比较宽松,不会出现死循环,而且最终答案$l,r$都可以用。但是缺点就是对于将要介绍的四种情况,转移时的$\pm 1$的位置变换很令人头疼。所以这里我将要使用的是后一种方式,但是左闭右闭一定要注意转移的写法l = mid + 1r = mid - 1,此时$\pm 1$都是固定的,但是最优解可能不在区间内,所以需要一个外层变量ans来确保得到的是最优解。这种写法的优点是非常好想。

二分法四种情况

需要二分答案的时候,要先确保数据具有单调性。也就是说给定一个集合$S$,里面有一个需要寻找的答案,那么有:如果$S_i$满足条件,那么所有$S_j(j\geq i)$(或者$j\leq i$),都满足条件,并且如果$S_i$不满足条件,则所有$S_j(j<i)$(或者$j>i$)都不满足条件,那么这个数据就具有单调性。

在单调的数据下,我们需要找一个满足条件的答案就可以用二分法。我们都学过二分搜索查找一个数,但是有时候我们不是查找一个数,而是找一个满足条件的最小/最大值呢?如果满足条件值并不存在呢?我们把所有情况分成四种以便区分。假设数据是一个非降序列,那么他们分别是:不小于条件最小位置,严格大于等于条件最小位置,不大于条件的最大位置,严格小于条件的最大位置。

不小于条件最小位置

假如给定一个非降序列:$S={1,1,4,4,5,6,7,8}$,假如我们想知道$S_i \geq 3$的最小位置,在此处显然是位置$3$,而不是位置$4$。在这种情况下,我们二分法找到$S_i$满足$S_i \geq 3$以后仍然要往更小的范围去寻找,这样才能保证是最小位置,那么在二分写法里面,就是将$r$的值缩小,那么最后一个满足条件的$mid$就是答案。由此可得一个写法:

1
int binary_search(int k) {
2
    int l = 1, r = n;
3
    int ans = n + 1; // 如果目标不存在就返回一个不存在的位置
4
    while (l <= r) {
5
        int mid = (l + r) / 2;
6
        if (arr[mid] >= k) {
7
        	ans = min(ans, mid);
8
            r = mid - 1;
9
        } else {
10
            l = mid + 1;
11
        }
12
    }
13
    return ans;
14
}

严格大于条件最小位置

我们换一个非降序列:$S={1,1,3,4,5,6,7,8}$,假如我们想知道$S_i > 3$的最小位置,那么我们可以看出应该是位置$4$,那么我们只需要把if (arr[mid] >= k)改成if (arr[mid] > k)就行了。

不大于条件的最大位置

假设这个序列是$S={1,1,3,3,3,6,7,8}$,然后我们要找一个$S_i \leq 3$的最大位置,那么我们可以看出应该是位置$5$。在此条件下,如果我们找到一个$S_i \leq 3$我们仍然需要往后找以确保能找到最大位置。那么在二分写法里面就是将$l$增大,那么我们只需要在此时找到最大的那个$mid$就是答案,写法如下:

1
int binary_search(int k) {
2
    int l = 1, r = n;
3
    int ans = 0; // 如果目标不存在就返回一个不存在的位置
4
    while (l <= r) {
5
        int mid = (l + r) / 2;
6
        if (arr[mid] <= k) {
7
        	ans = max(ans, mid);
8
            l = mid + 1;
9
        } else {
10
            r = mid - 1;
11
        }
12
    }
13
    return ans;
14
}

严格小于条件最大位置

我们只需要把if (arr[mid] < k)改成if (arr[mid] <= k)就行了。

其他情况

对于序列并非升序的情况,我们可以将它转化为升序思考。绝大部分二分的题都可以归结为这四种情况,像最大的最小值就是满足条件的最大位置,最小的最大值就是满足条件的最小位置。只要想清楚自己想要二分出来的答案是什么样的就可以轻松A掉题了。