二分法及其相关算法详解

二分法及其相关算法详解

二分法是一种随处可见却非常精妙的算法，经常能为我们打开解答问题的突破口。二分的基础的用法是在单调序列或单调函数中进行查找。因此当问题的答案具有单调性时，就可以通过二分把求解转化为判定（根据复杂度理论，判定的难度小于求解），这使得二分的运用范围变得广泛。进一步地，我们还可以扩展到通过三分发去解决单峰函数的极值以及相关问题。

1.整数集合上的二分

在一个单调递增的序列上查找$\ge x$$\ge x$数中较小的一个（即x以及x的后继，后半区间左闭）

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

在一个单调递增的序列上查找$\le x$$\leq x$数中较大的一个（即x以及x的前驱,前半右闭区间）

while(l < r){
    int mid = (l + r + 1) >> 1;
    if(array[mid] > x) r = mid - 1;
    else l = mid;
}
return array[l];

2.实数域上的二分

在实数域上二分较为简单，确定好所需的精度eps(一般为要求精度加2)，以l+eps<r为循环条件，每次根据在mid上的判定条件选择r=mid或l=mid分支之一即可。一般需要保留k为小数时，则取eps=${10}^{-\left(k+2\right)}$$10^{-(k+2)}$。

while(r - l < eps){
    double mid = (l + r) / 2;
    if(check(mid)) l = mid;
    else r = mid;
}
return l;

有时精度不容易确定或表示时，就干脆采用循环固定次数的二分方法，也是一种相当不错的策略，这种方法得到的结果的精度通常比设置eps更高

for(int i = 0; i < 100; ++i){
    double mid = (l + r) / 2;
    if(check(mid)) l = mid;
    else r = mid;
}
return l;

3.三分求单峰函数极值

有一类函数成为单峰函数，它拥有唯一的极值点，在该极值点的左侧严格单调递增，右侧严格单调递减，当然还存在左侧严格单调递减，右侧严格单调递增，我们也成后者为单谷函数。

现以单谷函数f为例进行说明，取其区间为$\left[l,r\right]$$[l, r]$，在其上任取两点lmid, rmid，把函数分为三段。

1. 若$f\left(lmid\right)<f\left(rmid\right)$$f(lmid) < f(rmid)$，则极小值点一定位于两者的左侧或者在两者之间，其中极小值点一定位于rmid的左侧，故r = rmid;

2. 若$f\left(lmid\right)>f\left(rmid\right)$$f(lmid) > f(rmid)$，则极小值点一定位于两者的右侧或者在两者之间，其中极小值点一定位于lmid的右侧，故l = lmid;

上述单调中一定为$严格单调$$\boldsymbol{严格单调}$

4.二分答案转化为判定

有些问题在解决的时候可以转化为二分的问题进行解决

相关练习