题目描述

二分模板

代码

// 找右区间最左数，或找大于某数(x)的最小数时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid =( l + r )/2;
        if (x<=a[mid])  // check()判断mid是否满足性质，按实际情况可选<= 或 <
            r = mid;     // l x mid r
        else 
            l = mid + 1; // l mid x r
    }
    return l;   //return r也可以
}
// 找左区间最右数，或找小于某数(x)的最大数时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid =( l + r + 1 )/2;
        if (a[mid]<=x)   //按实际情况可选<= 或 <
            l = mid;     // l mid x r  
        else 
            r = mid - 1; // l x mid r
    }
    return l;
}