二分模板及其原理

直接上代码

#include<bits/stdc++.h>
using namespace std;
//#define int long long       // 防止越界
//#defint double long double  // 防止越界
const int L=0,R=1e9+1;        // 整数二分边界 
// const double L=0,R=1e9+1;  // 实数二分边界
const double EPS=1;  // 实数二分误差 (修改为 1 即为整数二分)
bool check(int x){
    // do sth...
    return true;
}
bool check(double x){
    // do sth...
    return true;
}
int l,r,mid;       // 整数二分
// double l,r,mid; // 实数二分
signed main(){
    l=L,r=R;
    while(l+EPS<r){
        mid=(l+r)/2; // 二分
        if(check(mid)){ // 对答案的上下界进行修改
            l=mid;   // [l,r] -> [mid,r] 答案区间上移
            //r=mid; // [l,r] -> [l,mid] 答案区间下移
        }else{
            r=mid;   // [l,r] -> [l,mid] 答案区间下移
            //l=mid; // [l,r] -> [mid,r] 答案区间上移
        }
    }
    // 答案根据题目要求自行输出
    return 0;
}