笔记:二分法

前言

二分非常容易写错,尤其是面对不同的开闭区间和不同的单调性

本文着重总结二分法在不同情况的运用

关于二分查找和二分答案

我比较喜欢把他归为一类,因为二分答案和二分查找本身没有区别,更像是包含关系

何时用二分

二分的前提是单调性

如果存在 $f(x)$ 在某个区间具有单调性,这时候我们就可以对这个区间进行二分

二分模版

满足check函数的解有很多,但是有时候题目的解是唯一的最小或最大解

把所有的数从小到大排列,我们的check()结果就像一个折线

如果我们要找最小的解就取第一个true

同理取最大解就取最后一个true

$$\underbrace{\text{false, false, false, ...}}_{\text{不满足}} \underbrace{\text{true, true, true, ...}}_{\text{满足}}$$

最小可行解

int l=0, r=1e9;
while(l<r){
    int mid=(l+r)/2;
    if(check(mid)) r=mid;
    else l=mid+1;
}
cout << l;

最大可行解

int l=0, r=1e9;
while(l<r){
    int mid=(l+r+1)/2;
    if(check(mid)) l=mid;
    else r=mid-1;
}
cout << l;

浮点数二分

double l=0, r=1e9;
while(r - l > 1e-6){  // 精度要求
    double mid = (l + r) / 2;
    if(check(mid)) r = mid;
    else l = mid;
}
printf("%.6f\n", l);