算法 - 二分法

2020-08-05 09:07:32

二分法比较重要，然后又一定的模板。在此基础上可以进行一系列的修改，然后达到题目要求。需要注意有几个地方，二分法容易出错。

整数二分

二分法分整数二分和浮点数二分。

二分法使用的范围： 是以一个点，满足一个性质，可以把一个区间分成两个部分。这个性质可以是单调性也可以是其他的性质。

两个模板可以求两个点：

第一个求黑色点的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// l, r 分别表示left左边界，和r有边界。
// cheak() 表示是否中当前的划分的性质

int find(int arr[], int x) {
    int l, r;
    while (l < r) {
    int mid  = l + r + 1;
    if (cheak(mid)) l = mid;
    else r = mid - 1;
    }
    return l;
}

第二个球蓝色的点：

1
2
3
4
5
6
7
8
9
10
11
12
// l, r 分别表示left左边界，和r有边界。
// cheak() 表示是否中当前的划分的性质

int find(int arr[], int x) {
    int l, r;
    while( l < r) {
        int mid = l + r >> 1;
        if (cheak(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

二分的取整比较重要，有时候需要进行向上取证。不然就会一直进行循环。 当 l = mid 的时候需要进行向上取证，而 r = mid 不需要进行向上取整数。

  • l = mid的时候， 当l = r - 1, 如果是mid = l + r >> 1，如果cheak(mid) == true, 那么l = mid, 区间任然是[l, r]
  • 所以l = mid 的时候， mid = l + r + 1 >> 1; 进行向上取整数。
  • r不用此考虑，因为r本身就是向下取整，而且 while ( l < r) 当r向下取整后就会终止循环。
  • 所以在归并排序中mid = l + r >> 1, 左边分成[l, mid]右边是[mid + 1, r]区间。

浮点数二分

浮点数二分不用考虑边界情况，左边界和右边界都是一样的。以一个点向左划分和向右划分都是一样的。所以不存在划分的边界条件。

以开三次方为例子。数据范围 -1000000 <= n <= 1000000

1
2
3
4
5
6
7
8
double n;
double l = -100, r = 100;
while (r - l > 1e-8) {
    double mid = (l + r) / 2;
    if ( mid * mid * mid >= n) r = mid;
    else l = mid;
}
return l;
1
2
3
4
5
6
7
8
double n;
double l = -100, r = 100;
while (l < r) {
    double mid = (l + r) / 2;
    if (mid * mid * mid <= n) l = mid;
    else r = mid;
}
return l;

还有一种写法，就是循环100次数：

1
2
3
4
5
6
7
8
double n;
double l = -100, r = 100;
for(int i = 0; i < n; i++) {
    int mid = (l + r) / 2;
    if (mid * mid * mid >-= n) r = mid;
    else l = mid;
}
return l;

PS:

这里r - l > 1e-8 是提升精度的方式, 要求保留6位小数点的话，那么精度就要求1e8。循环100次也是提升精度的方式。 这里mid * mid * mid >= x， 等于符号无所谓，可有可无，因为取不到等于的情况。

  1. 1. 整数二分
  2. 2. 浮点数二分