算法笔记2：二分

二分

二分可以求得满足条件的左边界或右边界，如下图所示

查找左边界（绿色区域的最左边）：

int SL(int l, int r)
{
    while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid)) r = mid; 
            else l = mid + 1; 
        }   
    return l;
}

应用场景：

1. 找大于等于数的第一个数 （满足某个条件的第一个数）
2. 查找最小值 （满足该边界的左边界）

查找右边界（红色区域的最右边）：

int SR(int l, int r) 
{
    while (l < r)
        {                   
            int mid = l + r + 1 >> 1; //需要+1 防止死循环
            if (check(mid)) l = mid;
            else r = mid - 1; 
        }
    return r; 
}

应用场景：

1. 找小于等于数的最后一个数 （满足某个条件的最后一个数）
2. 查找最大值 （满足该边界的右边界）