整数二分

二分的本质是边界划分，给定一个区间，如下图，其中左半边表示满足某种性质，右半边表示不满足某种性质，可以通过这种性质来找到a,b这两个边界。

#include <iostream>

using namespace std;

//检查x是否满足某种性质
bool check(int num){/*-----*/}

//区间为[l,mid]和[mid + 1, r]时使用
int binary_search1(int l, int r){
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

//区间为[l,mid - 1]和[mid, r]时使用
int binary_search2(int l, int r){
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}