二分查找#

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

时间复杂度#

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

1
//往左找答案
2
while(l<r){
3
    int mid=l+r>>1;//(l+r)/2
4
    if(check(mid)){
5
        r=mid;
6
    }
7
    else{
8
        l=mid+1;
9
    }
10
}

1
//往右找答案
2
while(l<r){
3
    int mid=l+r+1>>1;//(l+r+1)/2
4
    if(check(mid)){
5
        l=mid;
6
    }
7
    else{
8
        r=mid-1;
9
    }
10
}

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

查找首个不小于给定值的元素：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//浮点二分

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

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