二分查找模板

模板原地址，从大佬那里习得的
另一位的解析，下面有更具体的分析
模板一共有两种，适用于两种不同的情况，第一种是：

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

我们通过实际数据来演示下查找过程

假如说我们用该算法查找以上数据中 8的坐标

经过第一次查询后,mid= (l+r)/2=2 结果5小于8 l=mid+1=3

第一次

经过第二次后 mid=(l+r)/2=4 结果9大于8 r=4

第二次
经过第三次查询后 mid=(l+r)/2=3 结果7小于8
此时l=mid+1=4
第三次

此次运行完之后，l==r==4
此时返回l=4 结果为9，值为数组中大于8的值中的最小值
到此模板1结束

---

模板2：

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

采用同样的数据，查找8

第一次查找后： mid=(l+r+1)/2=3 值为7小于8 l=mid=3

第一次

第二次查找后: mid=(l+r+1)/2=4 值为9大于8
此时r=mid-1=3

第二次
此时 l==r==3
返回结果为 7，为小于8的值中的最大值