今天来讲一讲二分查找
什么是二分查找？
我们先来看一个问题：
给你n个从小到大排列的数，叫你找一找，这n个数里有没有数m
比如：
n=4
1 2 3 4
m=2
因为我们可以在1 2 3 4中找到2，所以我们找到了，输出yes
但是，我们是怎么找的呢？
一般来讲，我们会想到用一个for，遍历一遍1 2 3 4，如果找到了2就输出，否则就输出no
但是这样是很没有效率的，如果用114514个数字，如果我们要说一堆数字中没有m，我们就要循环114514次，找每一个数，真是太没有效率了
那有什么办法可以让查找变得有效率，把性价比拉满呢？
我们仔细观察题目，我们注意到，这n个数都是从小到大排序的，这肯定是个关键信息，能帮助我们拉满性价比
那这个信息要怎么用呢？
当n=5，m=1，有1 2 3 3 5这几个数字的时候，我们首先找到五个数的中间数a[3]（中间数，是指数组最中间的数），如果m<a[3]说明m在a[3]的左边，也就是m在a[1~2]里（因为是从大到小排，所以如果小于了，我们就要到比a[3]还小的地方里去找），这时候中间数是a[1]，我们发现，a[1]=m,于是我们就找到了
二分查找怎么写？
Let's see the code!!!
//我们要在数组a中找key（有没有a[k]=key,有输出k）
//如果有多个a[k]=key,输出最小的k
//比如：1 1 1 2 3，key=1，则k=1
//l,r代表一个范围，就是说我们要在a[l]~a[r]之间找k
//l<=r
void cha(long long l,long long r,long long mid){
while(l<=r){//如果l<=r说明还能找，否则就是找不下去了，结束循环
mid=(l+r)/2;//mid是l，r的中间数（初中的中点公式）
//注意了，mid现在代表的是下标
//mid把l,r分成三个部分
//----------------------------------------------（这个虚线代表数组）
//l mid r 这里是下标
if(a[mid]==key){//这样就是找到了
if(mid<mi){//我们要找最小的，mi就是目前找到的最小的k
mi=mid;f=1;//mi变的更小，f=1表示有找到过
}
r=mid-1;//因为要找最小的，所以我们要往左边找
//往左边找，就是把r改变一下（可以结合上面的图）
}else if(a[mid]>key){//往左找←
r=mid-1;
}else if(a[mid]<key){//往右找→
l=mid+1;
}
}
}二分查找的应用：
具体的应用，等我以后写了题解在写吧
就讲到这了
二分查找很高效
