二分查找【详解】

二分查找【详解】_第1张图片

本期介绍

主要介绍:二分查找的简单思路,为什么必须在有序的前提下才能使用二分查找,该怎么用C程序来实现二分查找,二分查找的局限性。


目录

  • 简单思路
  • 前提条件
  • 编写程序
  • 总结

简单思路

当我们要从一个序列中查找一个元素的时候,最快想到的方法就是顺序查找法(即:从前到后依次查找)。但这种方法过于无脑,就是暴力的把每个元素都排查一遍。元素个数少的时候还行,一旦元素个数多起来,效率是非常低下,所以在实际中这种查找的方法是被摒弃的。

这里就不得不介绍一种简单且效率较高的查找方法了:二分查找法,又称折半查找法。但该方法是建立在有序的前提下的,基本思路就是:

先找到那个有序序列的中间元素mid,然后拿它和要找的元素K进行比较,就可以初步判断K所在范围,既然查找范围已确定,自然该范围之外的元素就可以不用再查找了(你看这样相较于顺序查找一下子就可以省略一半的元素不用查找了,这就是效率啊!!!)。当然接下来还会按照上面的步骤反复查找下去。

因为二分查找每一次查找都可以缩减掉一半的查找范围,由此可以知道二分查找法的时间复杂度是: log ⁡ 2 ( N ) \log_2(N) log2(N)。举个例子来解释该时间复杂度:若这里一共有2^32个元素,那么我在最坏的情况下也只需要32次就可以找到我想找的元素;而顺序查找法最坏的情况下,却需要查找 4,294,967,296‬ 次!!!,可见二分查找法的效率是非常之高的。


前提条件

都说二分查找法的前提条件是:查找的序列必须是有序的。我想大概很多小伙伴都会错误的认为有序是差值恒为1的顺序数列就像这样1、2、3、4、5、6、7、8、9)。这只不过是有序的某一种情况罢了,那何为有序呢?即该序列中的所有元素都是按照升序或者降序排列好的,元素与元素只间的差值虽然是随机的,但始终是在递增递减例如这样一个序列:3、12、24、31、46、48、66、79、82)。

那为什么二分查找的序列必须有序呢,而无序就不行?相信很多小伙伴都有此疑问,但却没有仔细的举例推敲。下面我举个例子:现有一个无序的序列如下图所示,我们要在其中查找是否存在元素77
二分查找【详解】_第2张图片
我们发现若是无序的序列,就算找到了中间的元素,也无法用它来判断所要查找元素所在的区间。如若硬是要使用二分查找法来查找元素(假想序列为递增),那么必然出错。就如上例,我们要查找元素77,而中间元素为100,可77小于100呀,所有我们认为我们所要找到的元素在100的左边,100及其右边都会被舍去。可眼睛告诉我们所要查找的元素77就在100右边呀,你怎么可以舍去呢?舍去后的结果自然是:查无此数呀!!!是错误的。
二分查找【详解】_第3张图片

除此之外,二分查找只能实现单值查找,不可能实现多值查找!!!所以总结一下:

二分查找有两个限制条件

  1. 查找的数量只能是一个,不能是多个
  2. 查找的对象在逻辑上必须是有序的

编写程序

上面介绍完二分查找的思路和其限制条件后,接下来就该讲一讲如何去实现代码了。就用该案来讲解吧:在下图所示序列中查找数字7,看是否能找到。
在这里插入图片描述

1. 第一步

首先,我们是要在一个有序的序列中查找某个元素的,那么该序列就必须有个连续的存储空间来存放,所以我们想到了用数组arr来存放。

#include
int main()
{
	//存储递增的有序数列
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
}

2. 第二步

接下来,就该是找到序列的中间元素了,那该怎么找?我提供一个思路:通过对数组元素下标的计算来找到中间元素(中间元素下标mid=(数组最左边下标left + 最右边元素下标right)/ 2)。
二分查找【详解】_第4张图片
程序如下所示:

#include
int main()
{
	
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//存储递增的有序数列
	int sz = sizeof(arr) / sizeof(arr[0]);//sz是数组元素的总个数
	int mid = 0;//存储中间元素的下标
	
	//左、右元素下标确定了被查找元素k的所在范围
	int left = 0;//最左边元素的下标
	int right = sz - 1;//最右边元素的下标
	int k = 0;//所要查找的元素k
	scanf("%d", &k);
	
	mid = (left + right) / 2;//计算中间元素的下标
}

3. 第三步

然后就拿中间元素和所查找元素k进行比较(这里我设置k = 7),发现7 > 5(中间元素),所以可以重新精确k的范围在中间元素之后了即:最左边元素应该为中间元素后面一个(left = mid + 1),最右边元素下标right不变。
二分查找【详解】_第5张图片
但其他的情况也不能忽略,k < mid时范围重新精确到了mid的左半部分,就是(right = mid - 1),left不变;还有当k = mid时就意味着:找到所要找的那个数了,就是mid下标所对应的那个数。程序如下:

#include
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//存储递增的有序数列
	int sz = sizeof(arr) / sizeof(arr[0]);//sz是数组元素的总个数
	int mid = 0;//存储中间元素的下标

	//左、右元素下标确定了被查找元素k的所在范围
	int left = 0;//最左边元素的下标
	int right = sz - 1;//最右边元素的下标
	int k = 0;//所要查找的元素k
	scanf("%d", &k);

	mid = (left + right) / 2;//计算中间元素的下标
	//判断mid和看大小,重新精确k所在范围
	if (arr[mid] < k)
	{
		left = mid + 1;
	}
	else if (arr[mid] > k)
	{
		right = mid - 1;
	}
	else
	{
		printf("找到了\n");
	}
}

4. 第四步

然后就是重复的去执行:找中间元素下标,比较mid和k大小,从而更新迭代k新的范围,直到mid = k(即找到k了)为止。既然要实现重复的循环,程序中自然就要用到循环体了呀,那就加进去一个循环嘛。写道这里可还没算完呢,我们循环条件是什么还没确定呢!那循环条件如何确定呢?先思考个问题:若一直没找到我们所要找的元素,程序会以怎样的方式结束呢?
二分查找【详解】_第6张图片
二分查找【详解】_第7张图片
二分查找【详解】_第8张图片
二分查找【详解】_第9张图片
思考后我们发现在查找一个元素的时候,left下标和right下标会越来越靠近,甚至会指向一处,这个过程中left始终在right的左边(即:left <= right)。但如果一直找不到那个元素,两个下标必然会相互交错(即: left > right),这时循环结束。所以循环条件总结下来就是:while(left <= right)

程序最终完成,如下所示:

#include
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//存储递增的有序数列
	int sz = sizeof(arr) / sizeof(arr[0]);//sz是数组元素的总个数
	int mid = 0;//存储中间元素的下标

	//左、右元素下标确定了被查找元素k的所在范围
	int left = 0;//最左边元素的下标
	int right = sz - 1;//最右边元素的下标
	int k = 0;//所要查找的元素k
	printf("请输入所要查找的数:");
	scanf("%d", &k);

	while (left <= right)
	{
		mid = (left + right) / 2;//计算中间元素的下标
	//判断mid和看大小,重新精确k所在范围
		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			break;
		}
	}
	if (left > right)
		printf("没有找到该数\n");
	else
	{
		printf("找到了\n");
	}
}

程序执行结果如下:
二分查找【详解】_第10张图片
二分查找【详解】_第11张图片


总结

我们在学习一种算法的时候,光听和空想可能并不怎么能清晰和透彻的认识它,我们应该上手去举几个例子来尝试一下,如若你还觉得不太理解,那就作图吧,这种方法是最直观的,基本上一画就懂。所以作图来学算法是yyds!!!


二分查找【详解】_第12张图片

这份博客如果对你有帮助,给博主一个免费的点赞以示鼓励欢迎各位点赞评论收藏⭐️,谢谢!!!
如果有什么疑问或不同的见解,欢迎评论区留言欧。

你可能感兴趣的