二分查找

二分查找，也叫折半查找，顾名思义就是从中间开始，一半一半的找目标

尽管我们查找数据的方法有很多（如枚举），但是有的方法一旦数据范围过大，程序就会炸掉（TLE），所以我们要使用二分法查找

至于二分法为何不会炸，因为它的时间复杂度为log(n)（每次都除2去找），所以它耗时少，经常被广泛使用于各类查找数据的题型

但它也有缺点，就是数组只能从大到小或从小到大排序，所以在某些时候，我们可以把它与sort一起用

原理及代码

假设我们有一个数组1~100，要查找其中的一个数x，我们首先可以猜50，这样当x<50时，我们就可以从1~50中继续折半查找（x>50同理），反复操作就可以找到需要的x值

代码：

int l=0,r=n+1;//避免死循环
while(l+1<r){
    int mid=(l+r)/2;//中点
    if(a[mid]>x){//a数组已输入
        l=mid;
    }else if(a[mid]<x){
        r=mid;
    }else{
        cout<<a[mid];
    }
}