【c++】二分查找教程

今天来讲一讲二分查找

---

什么是二分查找？

我们先来看一个问题：

给你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;
		}
	}	
}

---

二分查找的应用：

具体的应用，等我以后写了题解在写吧

---

就讲到这了

二分查找很高效