二分算法笔记

作者： 作者的头像   小思 ,  2021-05-05 22:19:12 ,  所有人可见 ,  阅读 525

2


3

本笔记内容来源于算法基础课

二分

整数二分

二分的本质不是单调性，但有单调性一定可以二分

二分的本质是边界：
对于区间[l, r]有，对于左子数组满足某种性质，对于右子数组不满足某种性质
二分则可以寻找左子数组的右边界或者右子数组的左边界，通过不断缩短含有目标答案的区间

基本步骤：

  1. 寻找中间值mid
  2. 判断中间值性质

寻找左子数组的右边界，check左边性质:

mid = l + r + 1 >> 1;
check(mid) == true  --> k in [mid, r]   --> l = mid
check(mid) == false --> k in [l, mid-1] --> r = mid-1

寻找右子树组的左边界，check右边性质：

mid = l + r >> 1
check(mid) == true  --> k in [l, mid]   --> r = mid
check(mid) == false --> k in [mid+1, r] --> l = mid+1

模板的选择：

1. l = mid --> mid = l + r + 1 >> 1;
2. r = mid --> mid = l + r  >> 1;

对于1当l = r-1 mid = l+1避免为true时陷入死循环

模板:
寻找满足性质的右边界

while (l < r) {
    int mid = l + r + 1 >> 1;
    if (check(a[mid]) <= k) l = mid;
    else r = mid - 1;
}

寻找满足性质的左边界

while (l < r) {
    int mid = l + r >> 1;
    if (check(a[mid])) r = mid;
    else l = mid + 1;
}

输出l r相同，因为循环结束时两者值相等
二分一定有解，因为边界必然存在

浮点数二分

同样是通过缩短区间寻找边界，但由于没有整数，只存在一个边界，因此会更加简单

迭代方式：

  1. 精度迭代：当r-l足够小时，输出边界
  2. 次数迭代：迭代次数取一个较大的数目，循环n次，区间长度会变成原来的$\frac{1}{2^n}$

精度范围比答案多保留两位

模板:
寻找满足性质的右边界

while (r - l > 1e-8) {
    double mid = (l + r) / 2;
    if (check(a[mid])) l = mid;
    else r = mid
}

寻找满足性质的左边界

while (r - l > 1e-8) {
    double mid = (l + r) / 2;
    if (check(a[mid])) r = mid;
    else l = mid
}

题目

对于求最小值或者最大值，可以采用二分，因为满足二段性

小于该值的都满足（不满足）条件，而大于该值的都不满足（满足）条件

所以结果就是满足性质的左边界或者右边界

LeetCode 410 二分最小最大值

Acwing 4080 巧妙check

0 评论