二分枚举

前言

二分查找的问题可以理解如下：在一个序列上，某个特定的标记将其分成左右两个部分。我们需要找到这个标记的位置在哪两个元素中间。当然，我们实际需要的显然不是这个标记，而是挨着标记的元素，因此二分查找一个需要特别注意的地方就是选取标记左边还是右边的元素返回。一个需要查找的序列可以抽象成下面的形状：(确实很抽象)

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□^□□□□□□□□□□□□□□□□□□□□□□□□□□□

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□^

^□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

一、线性枚举

1、定义

线性枚举指的就是遍历某个顺序表（如一维数组）的所有元素，找到满足条件的那个元素并且返回，返回值可以是下标，也可以是元素本身。

由于是遍历的，穷举了所有情况，所以一定是可以找到解的，一些资料上也称之为 暴力算法 （Brute Force）。

2、时间复杂度

线性枚举就是无脑遍历所有情况，并且在满足条件的第一时间退出循环。因此，当数组长度为 n 时，算法的时间复杂度为 O(n)，比较低效，我们需要更加高效的算法。（P社玩家特有的对*“高效”*的大力追求）

二、二分枚举

1、定义

二分枚举，也叫二分查找，指的就是给定一个区间，每次选择区间的中点，并且判断区间中点是否满足某个条件，从而选择左区间继续求解还是右区间继续求解，直到区间长度不能再切分为止。

由于每次都是把区间折半，又叫折半查找，时间复杂度为 O(logn)，和线性枚举的求解结果一致，但是高效许多，返回值可以是下标，也可以是元素本身。

2、举例说明

一个有序数组arr[]，要求找到元素3的位置。

[0,1,2,3,4,5,6,7,8,9]

3、算法分析

1）目标

找到特定元素的位置，由于解题之前我们不清楚数据大小和具体位置，为了提高效率的期望值，使用二分枚举是较好的选择。根据二分枚举的定义，一共有三个重点：区间、中点、条件。

2）区间框定

利用线性枚举的思路，我们引入游标的概念，只不过需要两个游标，左边一个右边一个，两者中间的区域就是我们框定的查找区间。为了包涵查找元素在头尾的情况，我们把游标初始位置都设置在数组以外。即对于一个n个元素的数组，左游标初始位置在-1，右游标初始位置在n。当然，如果你确定该元素不在两头了，也可以将左游标初始位置在0，右游标初始位置在n-1。这只需要先多一步头尾判断，好处是不容易出现越界。

[0,1,2,3,4,5,6,7,8,9]

↑———————————↑ （这里打——的原因是hexo渲染的时候会吞掉空格，——只是为了把↑放到正确的位置上。）

3）选择中点

我们将两个游标位置的差除以2，结果四舍五入取整，再加上原本左边游标的位置，从而得到两个游标的中点。注意，这一中点不一定正好就是两个游标正中间的位置，因为元素个数不一定是奇数。这只是对真正中点的一种靠近。

[0,1,2,3,4,5,6,7,8,9]

↑———–—↑————–—↑

4）条件判断

判断的条件，我们可以理解为前言提到的标记。标记不在序列上（因为只是一个判断函数），将序列分成两部分，目标与其紧邻。

在这个有序数组中，判断的方式就是和3比较大小。如果大于3，则证明中点在目标的右边。否则在左边。在我们的例子中，4>3，因此中点在3的右边。此时我们需要做的就是将右端点重置在中点的位置。这样就完成了一次二分，区间相比之前，缩小了一半。注意，我们要求的解，一定永远在 左游标 和 右游标 之间。

[0,1,2,3,4,5,6,7,8,9]

↑—–———↑

然后，我们继续选取游标的中点，并且判断中点的条件，进行重复操作，直到左右游标的位置差为1。此时无法继续进行二分，程序停止。

[0,1,2,3,4,5,6,7,8,9]

↑—-—↑–—↑

[0,1,2,3,4,5,6,7,8,9]

------—↑–—↑

[0,1,2,3,4,5,6,7,8,9]

———↑ -↑- ↑

[0,1,2,3,4,5,6,7,8,9]

————↑ -↑

此时左游标的位置就是我们这个问题要求的解。

当然，如果选取条件改变，也有可能最终的游标指向2、3，此时右游标的位置才是我们寻求的解。因此左右游标的选择需要根据条件判定的标准进行。

这个时候，这个时候 红色游标 和 绿色游标 的位置一定相差 1，并且 绿色游标 的位置就是我们这个问题要求的解。

4、源码详解

1）条件判定

判断一个元素在目标左还是右，我们可以单独用一个函数来实现。C语言实现如下：

1
2
3
int isRight(int val, int x) {
return val > x;
}

val > 3是一个判断语句，因此最后返回的结果将是0（不成立）或1（成立）。

2）二分枚举模板

接下来的二分枚举模板可以解决大部分二分枚举的问题，请妥善保管。

1
2
3
4
5
6
7
8
9
10
11
12
int binarySearch(int *arr, int arrSize, int x) { //(0)
    int l = -1, r = arrSize; // (1)
    int mid;
    while(r - l > 1) { // (2)
        mid = l + (r - l) / 2; // (3)
        if( isRight(arr[mid], x) ) // (4)
        	r = mid; // (5)
        else
        	l = mid; // (6)
        }
    return l; // (7)
}

(0) x是查找的目标元素；

(1) l 代表 左游标，r 代表 右游标；

(2) 当区间长度大于2的时候，二分缩小区间，这一步被称为 区间收敛；

(3) mid为计算出来的区间 [l, r] 的中点；

(4) 判断区间中点对应的元素符不符合条件；

(5) 如果符合，证明中点在目标元素右边(不然为什么叫isRight)，把右游标用中点游标替换。

(5) 如果 中点元素 是 绿色，则从 中点 到 r 的值都为 绿色，用 中点 替换 绿色游标；

(6) 如果不符合，证明中点在目标元素左边，把左游标用中点游标替换。

(7) 这个地方是模板需要变通的地方，如果目标在左游标处，那么应该返回l；反之，如果目标在右游标处，则应该返回r。这里是前者。

这由你的判断函数决定。无法判断的时候，可以将目标结果代入函数，看看函数是否成立，从而判断是左是右。

三、练习

  1. P1571 眼红的Medusa - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

int n = 0, m = 0;
int k[100010] = {0}, t[100010] = {0};

int isRight(int idx, int *a, int t)
{
    return a[idx] > t;
}

int binarySearch(int l, int r, int *a, int t)
{
    while (l + 1 < r)
    {
        int mid = l + (r - l) / 2;
        if (isRight(mid, a, t))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    return l;
}

int search(int *nums, int numsSize, int target)
{
    int a = binarySearch(0, numsSize - 1, nums, target);
    if (nums[numsSize - 1] == target) {
            printf("%d ", nums[numsSize - 1]);
            return 0;
        }
    else if (nums[a] == target) {
        printf("%d ", nums[a]);
        return 0;
        }
    else
        return -1;
}

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%d", &k[i]);
    for (int j = 0; j < m; ++j)
        scanf("%d", &t[j]);
    
    qsort(t, m, sizeof(int), cmp);
    for (int i = 0; i < n; ++i)
        search(t, m, k[i]);
    
    return 0;
}

  1. 704. 二分查找 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int isRight(int idx, int *a, int t) {
    return a[idx] > t;
}

int binarySearch(int l, int r, int *a, int t) {
    while(l + 1 < r) {
        int mid = l + (r - l) / 2;
        if( isRight(mid, a, t) ) {
            r = mid;
        }
        else {
            l = mid;
        }
    }
    return l;
}

int search(int* nums, int numsSize, int target) {
    int a = binarySearch(0, numsSize-1, nums, target);
    if(nums[numsSize-1] == target) return numsSize-1;
    else if(nums[a] == target) return a;
    else return -1;
}

  1. 1351. 统计有序矩阵中的负数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int isRight(int idx, int *a) {
    return a[idx] < 0;
}

int binarySearch(int l, int r, int *a) {
    while(l + 1 < r) {
        int mid = l + (r - l) / 2;
        if( isRight(mid, a) ) {
            r = mid;
        }
        else {
            l = mid;
        }
    }
    return r;
}

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize;
    int n = gridColSize[0];
    int cnt = 0;
    for(int i = 0; i < m; ++i) {
        cnt += ( n - binarySearch(-1, n, grid[i]) );
    }
    return cnt;
}