从入门到精通，30天带你学会C++【第十一天：二分查找】

目录

Everyday English

前言

二分查找

例题

50分做法

分析利弊

示例代码

示例截图

100分做法

二分查找是什么？

这题该怎么用二分查找？

示例代码

示例截图

结尾

---

Everyday English

Look before you leap.

三思而后行

前言

今天是2024年的第一天，新一年，新气象，新起点，在这也祝愿大家：

工作顺利，身体健康。好好学习，天天向上！

二分查找

二分法我们在上节课已经介绍过了，这节课我们来实现二分查找。

没看过的一定要先看：

从入门到精通，30天带你学会C++【第十天：猜数游戏】-CSDN博客文章浏览阅读2次。【全网最细】猜数游戏他终于来了，内涵必胜策略哦！https://blog.csdn.net/m0_73787047/article/details/135323413

例题

先看题目：给定一个长度为n序列和一个整数m，问：这个序列里面有没有m？

50分做法

分析利弊

把整个数组遍历一遍，看看有没有m。

优点：简单粗暴，容易想到。

缺点：数据一多，轻松超时。

示例代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,m,a[100000];
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]==m) 
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

示例截图

100分做法

这就需要用到我们的二分查找了。

注意：二分查找一定要是有序的序列！

二分查找是什么？

回忆一下我们上次的猜数游戏的必胜策略，从始至终都是有一个范围的，我们通过不断地把范围二分缩小，最终得到答案。

在二分查找中也要有一个范围，或者叫区间。在这个区间有两个端点，分别叫左端点和右端点。

那我们二分还得有个中点，就像猜数游戏每次都要猜区间地一半一样。

而中点地计算方法是：（左端点+右端点）/ 2

为了方便描述，我们在编程中一般把左端点叫作left，右端点叫作right，中点叫作mid。

这题该怎么用二分查找？

我们可以先把序列用sort排序一下，紧接着确定好左右端点及mid。

其实这两个端点就像两个指针一样

如果left+1==right的话，说明两个指针不能在缩小了，此时，如果还未找到输出no。

示例代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,m,a[100000],left,right,mid;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	left=1; right=n;
	while(left+1!=right)
	{
		mid=(left+right)/2;
		if(a[mid]>m) right=mid-1;
		if(a[mid]<m) left=mid+1;
		if(a[mid]==m)
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

示例截图

结尾

最后认识一下，我是爱编程的小芒果，一个爱编程的小学生，我们2024年见！