二分_解题技巧

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 274 阅读时长 ≈ 1 分钟

适用范围

  1. 能找到确切的答案边界范围
  2. 答案的分布具有单调性

满足上述两点就可以尝试二分答案搜索了~

一般来说，会有最大求最小、最小求最大、在误差精度的范围内等等字眼

模板

答案二分的伪代码模板如下

1
2
3
4
5
6
7
8
9
10
while(l <= r){
    //l和r都要可取
    mid = l + (r - l) / 2;
    //防止溢出
    if(check(mid))
        //向右边界移动就是 l = mid + 1
        //向左边界移动就是 r = mid - 1
}
//如果求的是右边界, return r
//如果求的是左边界，return l

实数二分的伪代码模板如下，可通过该模板题熟悉：

1
2
3
4
5
6
7
8
9
while(r - l > eps){
    //eps是精度范围
    mid = (l + r) / 2;
    if(check(mid))
        //向右边界移动就是 l = mid
        //向左边界移动就是 r = mid
}
//如果求的是右边界, return r
//如果求的是左边界，return l

贴士

STL自带的俩函数：

  • lower_bound函数是找到第一个大于或等于

  • upper_bound函数是找到第一个大于

可通过P1678来熟悉