二分模板

1.二分模板

二分的本质并不是单调性，而是一种边界。

定义某种性质，使得右半边的部分全部满足该种性质，而左半边的部分全部都不满足该种性质。而二分可以寻找性质的边界。

image-20230318212326710

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//区间[low, high]被划分成[low, mid - 1]和[mid, high]时使用:
while (low < high) {
    int mid = low + high + 1 >> 1;
    if (check(mid)) low = mid;
    else high = mid - 1;
}
//区间[low, high]被划分成[low, mid]和[mid + 1, high]时使用:
while (low < high) {
    int mid = low + high >> 1;
    if (check(mid)) high = mid;//check判断mid是否满足性质
    else low = mid + 1;
}
//小数二分
const double eps = 1e-6;//eps表示精度 取决于题目对精度的要求
while (high - low > 1e-8) {
    double mid = (low + high) / 2;
    if (check(mid)) low = mid;
    else high = mid;
}

1.AcWing789.数的范围

image-20230318214210933

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
#include<iostream>
using namespace std;

const int MAX = 1e6 + 10;

int n, m, arr[MAX];

//整数二分模板
//思路：对数组进行二分 分别查找某个数字出现范围的起始坐标与终止坐标
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);
    for (int i = 0; i < m; ++i) {
        int x;
        scanf("%d", &x);
        //查找数字x出现的起始坐标 low == high
        //区间[low, high]被划分成[low, mid]和[mid + 1, high]时使用:
        int low = 0, high = n - 1;
        while (low < high) {
            int mid = low + high >> 1;
            if (arr[mid] >= x) high = mid;
            else low = mid + 1;
        }
        if (arr[low] != x) printf("-1 -1\n");
        else {
            printf("%d ", low);//起始坐标
            //查找数字x出现的终止坐标 low == high
            //区间[low, high]被划分成[low, mid - 1]和[mid, high]时使用:
            int low = 0, high = n - 1;
            while (low < high) {
                int mid = low + high + 1 >> 1;
                if (arr[mid] <= x) low = mid;
                else high = mid - 1;
            }
            printf("%d\n", low);//终止坐标
        }
    }
    return 0;
}

2.AcWing790.数的三次方根