acwing算法笔记-二分

二分问题

第一篇二分搜索论文是 1946 年发表，然而第一个没有 bug 的二分查找法却是在 1962 年才出现，中间用了 16 年的时间。

由此可以看出，二分其实看似思想简单，但其实实操时极其容易出错，所以我们来仔细探讨一下二分的思想。

首先二分的本质是二段性而不是单调性。

一个题目,如果一个区间具有单调性质,那么一定可以二分,但是如果说这道题目没有单调性质,而是具有某种区间性质的话,我们同样可以使用二分.

首先二分问题分为整数二分和浮点数二分，整数二分的边界问题更多，所以我们先来看整数二分。


整数二分

二分的本质是边界。假设在一个区间上定义了某种性质，整个区间可以被一分为二，使得这个性质在右半段区间满足而在左半段不满足。二分可以寻找边界，既可以找到左半段的右边界a，也可以找到右半段的左边界b。

1
2
l       ab                  r
xxxxxxxxxoooooooooooooooooooo

这里是课上更直观的画图：
p1

所以对于求两个边界，二分模板一共有两个，分别适用于不同情况。

1. 寻找右段的边界点（左边界）
在右半段寻找左边界（即寻找符合性质的第一个点） = 满足性质的边界值（绿色区域的左边界值）

  1. 找中间值 mid = (l+r)/2
  2. if(check(mid))等于true或者是false
    check(m)是检查m是在满足性质的区间（检查是不是在绿色区间）
  3. 更新l或者r
    p2
    我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1

2. 寻找左段的边界点（右边界）

在左半段寻找右边界（即寻找不符合性质的最后一个点） = 不满足性质的边界值（红色区域的右边界值）

  1. 找中间值 mid = (l+r+1)/2
  2. if(check(mid))等于true或者是false
    check(m)是检查m是在不满足性质的区间（检查是不是在红色区间）
  3. 更新l或者r
    p3
    我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid

图里的答案就是指边界点，二分找的是边界点


代码模板

模板1-左边界

1
2
3
4
5
6
7
8
9
10
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

模板2-右边界

1
2
3
4
5
6
7
8
9
10
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

怎么记忆呢，如果是找左边界，r = mid (r = mid, 区间划分[l, mid], [mid + 1, r] 所以 l = mid + 1)
右边界的话，l = mid, (l = mid, 区间划分[mid, r], [l, mid - 1] 所以 r = mid - 1)
然后mid = l + r >> 1这里是否 + 1 根据口诀（有减必有加）
注意mid的定义是在while循环里面

二分基本思路：
首先将问题抽象成找某段范围内的边界点
然后判断是左边界，还是有边界
之后应用模板


789. 数的范围

基本思路

找两个点，一个是数值>=x的第一个点（左边界），一个是数值<=x的最后一个点（右边界）
范围：数组范围
边界点：左右边界

参考代码

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
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    while (m -- )
    {
        int x;
        scanf("%d", &x);

        int l = 0, r = n - 1;
        //第一个>=x的点
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if (q[l] != x) cout << "-1 -1" << endl;
        else
        {
            cout << l << ' ';

            int l = 0, r = n - 1;
            //最后一个>=x的点
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }

            cout << l << endl;
        }
    }

    return 0;
}

常见问题

1. mid = l+ r >> 1, mid = l + r + 1 >> 2为什么在两个模板里，mid的取值会不同？
如果更新是l = mid, mid = l + r >> 1是向下取整，可能会取到l,那么更新过后的区间[mid , r]有可能是[l, r]这样就会造成无限划分，死循环。

同理如果更新是r = mid, mid = l + r + 1 >> 1是向上取整，可能会取到r，那么更新过后的区间[l, mid]有可能是[l, r],这样也会造成无限划分，死循环。

简单技巧：先写成mid = l + r >> 1,然后看更新后的区间，然后避免出现[l , r]的情况（因为会造成无限划分死循环），由此判断mid是否+1。

2. 为什么是while (l < r)?
这个地方实际上就是类似于分治，一直缩小区间长度，当l = r时，我们就找到了目标值。循环停止时肯定有l = r。


算法分析

时间复杂度

二分查找，每次都是折半查找，可以通过迭代或者递归实现。
如果是迭代法，也就是我们所用的模板，从长度n一直查找到长度为1，所以一共迭代了log(n)次，每次操作仅仅是通过索引取mid，很显然操作是O(1)，总时间就是O(logn)。
如果是递归法，很显然可以看出一共递归了log(n)次，每次是O(1)，也可以得出时间复杂度为O(logn)

空间复杂度

递归法会消耗函数栈空间，递归log(n)次，空间复杂度为O(logn).
迭代法空间复杂度为O(1),所以对于二分查找我们一般采取迭代法。


Reference

[1]. 图解 y总的二分模板 （最容易理解版本 )
[2]. 二分模板笔记

浮点数二分

浮点数二分比整数二分简单多了，因为不需要考虑边界处理。
基本思想与整数二分完全相同，也是分左边界和右边界，只不过在一次二分中，这两个点可以无限逼进，通常是函数求根、开方等问题，比较简单，while循环终止条件是精度e，更新时l和r都更新为mid即可。


代码模板

1
2
3
4
5
6
7
8
9
10
double bsearch_3(double l, double r)
{
    while (r - l > 精度)
    {
        double mid = (l + r) / 2;   //这里不需要考虑取整，因为是浮点数
        if (check(mid)) r = mid;    //这里需不需要考虑 +1 -1 之类的，因为是浮点数
        else l = mid;
    }
    return l;
}

1
2
3
4
5
6
7
8
9
10
double bsearch_4(double l, double r)
{
    while (r - l > 精度)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;    //只有这两个地方与上面的模板相反，其余都一样
        else r = mid;
    }
    return l;
}

790. 数的三次方根

基本思路

找num的三次方>=x的左边界
范围：-10000 ~ 100000
边界点：左边界

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = -100, r = 100;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }

    printf("%.6lf\n", l);
    return 0;
}

一般r - l > 精度，这里的精度是比答案要求高2个精度


相关题目

[1]. LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

算法 > AcWing
#算法 #二分
acwing算法笔记-二分
https://vendestine.com/binary-search
Author
Wenzhe Li
Posted on
March 19, 2022
Licensed under