02二分

二分

问题

适用于一个序列，有一个check函数，能够使得序列左边都返回false，右边都返回true，然后我们找的就是这个分界点的时候

基本思想

两种情况
一种是求 左半段最后一个元素，也就是说求上界，比如求 小于等于 x 的最后一个元素
这时候 mid = l + r + 1 >> 1;

bool check(int mid , int x){
    return q[mid] <= x;
}
if(check(mid,x)) l = mid;
else r = mid - 1;

另一种情况是求 右半段的第一个元素，也就是求下界，比如求 大于等于 x 的第一个元素
这时候 mid = l + r + 1 >> 1;

bool check(int mid , int x){
    return q[mid] >= x;
}
if(check(mid,x)) r = mid;
else l = mid + 1;

模板

给定一个序列 q , 求大于等于 x 的第一个值 右半段的第一个

bool check(int mid , int x){
    return q[mid] >= x;
}
int l = 0, r = n - 1, mid;
while (l < r)
{
    mid = l + r >> 1;
    if (check(mid, x)) r = mid;
    else l = mid + 1;
}
if(q[l] == x) ...

给定一个序列 q , 求小于等于 x 的最后一个值 左半段的最后一个

bool check(int mid , int x){
    return q[mid] <= x;
}
int l = 0, r = n - 1, mid;
while (l < r)
{
    mid = l + r + 1 >> 1;
    if (check(mid, x)) l = mid;
    else r = mid - 1;
}
if(q[l] == x) ...