【c++】二分查找教程

2023-12-28 22:34:25

今天来讲一讲二分查找


什么是二分查找?

我们先来看一个问题:

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

二分查找的应用:

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


就讲到这了

二分查找很高效

文章来源:https://blog.csdn.net/ptyz306/article/details/135278620
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。