Dichotomy (integer dichotomy, real dichotomy)

Two 、 Two points

Search method in monotone sequence or monotone function .（ Termination conditions ：l=r）

Integer field dichotomy

analysis

• Pay attention to the end boundary 、 Left and right intervals .

（1） Narrow the scope of ：r=mid,l=mid+1, Median value ：mid=(l+r)>>1.

（2） Narrow the scope of ：l=mid,r=mid+r, Median value ：mid=(l+r+1)>>1.

The first kind won't get $r$ This value , The second kind won't get $l$. It can be used to deal with the situation of no solution . The first two partitions are from [1,n] Expand to [1,n+1] and [0,n], If the last two points stop at this out of bounds subscript , There is no solution. .

huangzh

• Right shift operation rounding down , Integer division rounds zero .

Templates

Example

789. The range of numbers - AcWing Question bank

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int n,q,k;
int main(){
    
    cin>>n>>q;
    for(int i=0;i<n;i++)cin>>a[i];
    while(q--){
    
        int k;
        cin>>k;
        int l=0,r=n-1;
        while(l<r){
    
            int mid=l+r>>1;
            if(a[mid]>=k)r=mid;
            else l=mid+1;
        }
         
        if(a[l]!=k)cout<<"-1 -1"<<endl;
        else {
    
            cout<<l<<" ";
            l=0,r=n-1;
            while(l<r){
    
                int mid=l+r+1>>1;
                if(a[mid]<=k)l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}

Real number field dichotomy

analysis

• Pay attention to accuracy
  Using the bisection method with fixed number of cycles to solve the problem of accuracy .（ Precision than eps high ）

Templates

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

Example

790. The third root of a number - AcWing Question bank

• eps Accuracy requirements for

#include <iostream>
using namespace std;
int main(){
    
    double n;
    cin>>n;
    double l=-10000,r=10000;
    while(r-l>1e-8){
    
        double mid=(l+r)/2;
        if(mid*mid*mid>=n)r=mid;
        else l=mid;
    }
    printf("%.6lf",l);
    return 0;
}