整数域

2种边界

[l,r] （左闭又闭 容易理解最好用）

#include<iostream>
using namespace std;
int main(){
    int l,r;
    int n;
    cin>>n;
    while(l<=r){
        int mid=(l+r)>>1;//向下取整
        if( calc(mid) < n ) l=mid+1;
        else r=mid-1;
    }
    return 0;
}

[l,r+1) (左闭右开 )

#include<iostream>
using namespace std;
int main(){
    int l,r;
    int n;
    cin>>n;
    while(l<r){
        int mid=(l+r)>>1;
        if( calc(mid) < n ) l=mid+1;
        else  r=mid;// mid需要取到
    }
    return 0;
}

实数域

设置一个需要的精度 eps( 需要确定到小数点的后几位 1ek ) 以 l+eps<r作为循环条件

#include<iostream>
using namespace std;
int main(){
    double  l,r;
    cin>>l>>r;
    while( l+eps< r ){//eps代表需要确定到小数点后几位
        double mid=(l+r)/2;//实数不需要注意取整
        if( calc(mid) ) ans=mid,l=mid;
        else r=mid;
    }
    return 0;
}

如果一个问题的结果具有单调性（结果在所给出的定义域中），那么也可以用二分寻找结果

例题：

N本书排成一行，第i本的厚度为$a_i$，把它们分成连续的M组，使T最小化，T是厚度之和最小的一组,求最小的T是多少？

思路：在[0,总厚度]中二分，如果按照二分厚度可以分成m组（大于m也行）那么记录并且维护最小t

#include<iostream>
using namespace std;
const int maxn=10000;
int a[maxn];
int n,m;//n本书，m组
bool valid(int k){//k是给出的最大组的厚度，
    int group=1,rest=k;
    //题目说的是连续的M组，否则不能这样分组
    for(int i=1;i<=n;i++){
        if(rest >= a[i])   rest-=a[i];
        else group++,rest=k-a[i];
    }
    return group<=m;//分的组数少，t越小，则成立，分的组数多使的t少，那么不成立
}
int main(){
    int ans=0;
    cin>>n>>m;
    int sum=0;
    for(int i=1;i<=n;i++)   cin>>a[i],sum+=a[i];
    int l=0,r=sum;
    while(l<=r){
        int mid=(l+r)>>1;
        if( valid(mid) ) ans=mid,r=mid-1;//只要有效，一直记录最小值
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}