【C语言】带你玩转经典算法用二分法在一个有序数组中查找某个数

雨点打透心脏的1/2处 2024-03-16 18:26 38阅读 0赞

![在这里插入图片描述][3b5ce6acb987412b9ce66515e086c46d.png_pic_center]

[君兮\_的个人主页][Link 1]

**勤时当勉励 岁月不待人**

**C/C++ 游戏开发**

--------------------

#### 在有序数组中快速查找某个数 ####

*  前言
 *  一.经典法
 *  二.分法查找
 *   *  1.什么是二分法？
     *  2.二分法的使用
     *  3.二分法的优点与缺陷
 *  总结

## 前言 ##

> **二分法在C语言初阶中是一种非常经典的算法，今天就来带大家认识一下它。**

## 一.经典法 ##

> 利用循环与判断语句通过遍历的方式实现

*  代码如下：

int main()
    {
        
    	int arr[] = {
         1,2,3,4,5,6,7,8,9,10 };//升序
    	int k = 7;
    	int i = 0;
    	for (i = 0; i < 10; i++)
    	{
        
    		if (arr[i] == k)
    		{
        
    			printf("找到了，下标是:%d\n", i);
    			break;
    		}
    	}
    	if (i == 10)
    	{
        
    		printf("找不到\n");
    	}
    	return 0;
    }

*  这样雀氏能达到我们的目的，但是转念想想，是不是有点太大材小用了？
 *  如果这个数组并不是一个有序数组，我们依然能用这种方法达到我们的目的
 *  但是于此同时，由于我们每个数都要判断一遍，这大大增加了我们的时间复杂度。
 *  有没有更加简单且时间复杂度更低的算法呢？
 *  当然有，下面我们来介绍一下通过二分法实现在有序数组中的查找。

## 二.分法查找 ##

### 1.什么是二分法？ ###

*  首先对于一个有序数组，它一定是满足升序或者降序的(即前一个数的值一定比后一个数小(大))。
 *  **而我们的二分法查找，它只适用于在有序数组里查找某个数**
 *  画图解释一下  
    ![在这里插入图片描述][1e7a2731dd4e409c8ff9cfc99d3d64dc.png]
 *  了解了二分法的基本原理，我们来具体实现一下

### 2.二分法的使用 ###

*  还是通过代码来讲解一下

int main()
    {
        
    	int arr[] = {
         1,2,3,4,5,6,7,8,9,10 };//升序
    	
    	int k = 7;
    	int i = 0;
    	int sz = sizeof(arr) / sizeof(arr[0]);//利用数组的总大小除以数组中一个元素的大小，得到数组中一共存放了几个元素
    	//1
    	int left = 0;
    	int right = sz-1;//数组下标是数组元素个数-1
    	int flag = 0;//flag的作用是标志是否找到了
    	//2
    	while (left<=right)//当左右都指向同一个数时还没找到，说明此数不存在
    	{
        
    		int mid = (left + right) / 2;
    		if (arr[mid] == k)
    		{
        
    			printf("找到了,下标是:%d\n", mid);
    			flag = 1;//令flag等于1
    			break;
    		}
    		else if (arr[mid] < k)//mid就比k小，舍去比mid更小的数
    		{
        
    			left = mid + 1;
    		}
    		else//mid比k大，舍去比mid大的数
    		{
        
    			right = mid - 1;
    		}
    	}
    	//1 2
    	if (flag == 0)//判断是否找到k，如果找到，flag应等于1
    		printf("没找到\n");
    
    	return 0;
    }

*  运行结果如下  
    ![在这里插入图片描述][d1a6c612d502450dbc3eb2ca8ea89763.png]  
    为了防止某些初学者还是没弄懂，我们这里也画个图说明一下。
 *  **注意：由于left right mid均是整型，当出现小数是会自动把小数给舍去**
 *  假设此时的k=7
 *  在上面的代码的注释中，我解释了中间值mid的由来。这里不再缀叙。  
    ![在这里插入图片描述][12c02745b0b4457286913cc733593a28.png]  
    \-此时锁定的k的范围为  
    ![在这里插入图片描述][280aa7b8f0bc4d1e8995ce5dfd7bb610.png]
 *  第二次比较后，mid反而比k大了，那么就要舍去比mid还大的数。此时k的范围：  
    ![在这里插入图片描述][b52ebe8634054624ab10bc78c1df3fd4.png]
 *  **此时mid与left指向了同一位置，但是mid此时仍然小于k，Left=mid+1，当出现这种情况时，Left，Right，mid均指向数组下标为6的元素，如果此时还找不到k，说明这个数组中就没有看，但在图中这种情况，此时mid值与k相等，我们找到了我们想要的k，下标是mid**。  
    ![在这里插入图片描述][10dae67526264b3995c80e194f0d3088.png]

### 3.二分法的优点与缺陷 ###

*  **通过上面两种方法的对比我们可以很明显的看出来，二分法的时间复杂度要远远小于经典法，比如咱们要从一个四位数中找某个数，经典法可能要运行个几千次才能找到，而对于二分法来说，可能十次不到就解决了**
 *  **但是万事都是有利必有弊的，对于二分法来说，它的使用条件仅限于在一系列有序数中查找某个数，一旦在这个数组是无序的，那么二分法就无法满足我们查找的要求，而经典法通过遍历就能实现我们的要求。**

## 总结 ##

*  二分法虽好但有严苛的使用条件，在我们实际应用的过程中，一定要结合实际要求来选择是使用二分法还是经典法，万万不可不分情况随意使用。
 *  好了，以上就是今天的主要内容了，如果你有什么疑问欢迎在评论区提出或者私信我哦，博主看到会第一时间回复滴！

> ***如果觉得今天的内容对你有用的话，不妨点个三连再走啊，感谢大家的支持，你们的支持就是我更新的动力！！！***

![在这里插入图片描述][3f3dcaf156eb427e8fb4f8c272ae8a18.jpeg_pic_center]

[3b5ce6acb987412b9ce66515e086c46d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7eed8392cca74e5bb90f8865cf6bc873.png
[Link 1]: https://blog.csdn.net/syf666250?spm=1010.2135.3001.5343
[1e7a2731dd4e409c8ff9cfc99d3d64dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/057795aec8274297a67dfeb66dd9ff27.png
[d1a6c612d502450dbc3eb2ca8ea89763.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/df6d3dab8b104d24928d90a3eadf8ff7.png
[12c02745b0b4457286913cc733593a28.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/55ae4dbec3bf4e0e93d36f57cef8ddb2.png
[280aa7b8f0bc4d1e8995ce5dfd7bb610.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1d9f52829a6343a0b10fff6715848a2b.png
[b52ebe8634054624ab10bc78c1df3fd4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7b3a531cd5004a4c95516126eb92d825.png
[10dae67526264b3995c80e194f0d3088.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b8a3851dbc114eb08368392a90198b65.png
[3f3dcaf156eb427e8fb4f8c272ae8a18.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/785162e7b15b406f8b9b053ffc79017b.png