二分查找【详解】

在这里插入图片描述

本期介绍🍖

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

目录🍖

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

简单思路🍖

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

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

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

因为二分查找每一次查找都可以缩减掉一半的查找范围，由此可以知道二分查找法的时间复杂度是: $log_2(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。

我们发现若是无序的序列，就算找到了中间的元素，也无法用它来判断所要查找元素所在的区间。如若硬是要使用二分查找法来查找元素（假想序列为递增），那么必然出错。就如上例，我们要查找元素77，而中间元素为100，可77小于100呀，所有我们认为我们所要找到的元素在100的左边，100及其右边都会被舍去。可眼睛告诉我们所要查找的元素77就在100右边呀，你怎么可以舍去呢？舍去后的结果自然是：查无此数呀！！！是错误的。

除此之外，二分查找只能实现单值查找，不可能实现多值查找！！！所以总结一下：

二分查找有两个限制条件：

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

编写程序🍖

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

1. 第一步👀

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

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

2. 第二步👀

接下来，就该是找到序列的中间元素了，那该怎么找？我提供一个思路：通过对数组元素下标的计算来找到中间元素（中间元素下标mid=（数组最左边下标left + 最右边元素下标right）/ 2）。

程序如下所示：

#include<stdio.h>
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;//所要查找的元素kscanf("%d", &k);mid = (left + right) / 2;//计算中间元素的下标
}

3. 第三步👀

然后就拿中间元素和所查找元素k进行比较（这里我设置k = 7），发现7 > 5(中间元素)，所以可以重新精确k的范围在中间元素之后了即：最左边元素应该为中间元素后面一个（left = mid + 1），最右边元素下标right不变。

但其他的情况也不能忽略，k < mid时范围重新精确到了mid的左半部分，就是（right = mid - 1），left不变；还有当k = mid时就意味着：找到所要找的那个数了，就是mid下标所对应的那个数。程序如下：

#include<stdio.h>
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;//所要查找的元素kscanf("%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了）为止。既然要实现重复的循环，程序中自然就要用到循环体了呀，那就加进去一个循环嘛。写道这里可还没算完呢，我们循环条件是什么还没确定呢！那循环条件如何确定呢？先思考个问题：若一直没找到我们所要找的元素，程序会以怎样的方式结束呢？

思考后我们发现在查找一个元素的时候，left下标和right下标会越来越靠近，甚至会指向一处，这个过程中left始终在right的左边（即：left <= right）。但如果一直找不到那个元素，两个下标必然会相互交错（即: left > right），这时循环结束。所以循环条件总结下来就是：while（left <= right）。

程序最终完成，如下所示：

#include<stdio.h>
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;//所要查找的元素kprintf("请输入所要查找的数：");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");}
}