二分查找

具体思路为每次查找时，将范围折半，判断查找数的位置并将其折半，重复以上操作就可快速得出答案。注意操作时必须保证数组是有序的！！

时间复杂度

二分的最坏复杂度为 $O(log N)$

//往左找答案
while(l<r){
    int mid=l+r>>1;//(l+r)/2
    if(check(mid)){
        r=mid;
    }
    else{
        l=mid+1;
    }
}

//往右找答案
while(l<r){
    int mid=l+r+1>>1;//(l+r+1)/2
    if(check(mid)){
        l=mid;
    }
    else{
        r=mid-1;
    }
}

while(r-l<1e-5){//注意所有类型都为double
    double mid=(l+r)/2;
    if(check(mid)){
        l=mid;
    }
    else{
        r=mid;
    }
}

查找首个不小于给定值的元素：lower_bound：

使用时直接调用lower_bound( ForwardIt first, ForwardIt last, const T& value );，使用时必须保证数组有序。

如果没有找到，返回last

查找首个大于给定值的元素： upper_bound：

使用时直接调用upper_bound( ForwardIt first, ForwardIt last, const T& value );，使用时必须保证数组有序。

如果没有找到，返回last

P1163//浮点二分

在题目的答案有一个很大的区间，且保证这个区间对题目中的某一个量具有单调性，就可以使用二分答案来解决问题。

形式化的来说，一道题目如果符合以下条件就可以使用二分答案来求解。