查找算法实现【C语言实现】

清疚 2023-02-24 13:25 2阅读 0赞

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

**目录**

1. 线性（顺序）查找法

2. 二分查找算法

3. 插值查找算法

4. 分块查找算法

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

### 1. 线性（顺序）查找法 ###

查找算法是指：从一些数据之中，找到一个特殊的数据的实现方法。查找算法与遍历有极高的相似性，唯一的不同就是查找算法可能并不一定会将每一个数据都进行访问，有些查找算法如二分查找等，并不需要完全访问所有的数据。

#include <stdio.h>
    
    int target = 10;
    int unFind = 11;
    int array[] = { 2, 3, 4, 6, 8, 10, 12 };
    int len = sizeof(array) / sizeof(array[0]);
    
    // 顺序查找法
    int findBySeq(int *a, int len, int target){
    	for (int i = 0; i < len; i++){
    		if (a[i] == target){
    			return i;
    		}
    	}
    	return -1;
    }
    
    
    int main(){
    	printf("start testing --- \n");
    	int res;
    
    	res = findBySeq(array, len, target);
    	printf("result is : %d \n", res);
    
    
    }

### 2. 二分查找算法 ###

二分查找也称折半查找（Binary Search），多数的人喜欢叫他二分查找。它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列，**注意必须要是有序排列**，但有一种特殊情况可以不必须有序排列，即前一节介绍的商品选取，从一堆标准重量为10的商品中查找出唯一的次品，这种特殊的数据情况也可以使用二分查找。

#include <stdio.h>
    
    int target = 10;
    int unFind = 11;
    int seq[] = { 1, 2, 3, 5, 7, 9, 10, 12 };
    int len = sizeof(array) / sizeof(array[0]);
    
    int binarySearch(int *array, int len, int target){
    	int low = 0;
    	int high = len - 1;
    	int middle;
    
    	while (low <= high){
    		middle = (low + high) / 2;
    		if (array[middle] < target){
    			low = middle + 1;
    		}else if (array[middle] > target){
    			high = middle - 1;
    		}else{
    			printf("找到数值,位置为 %d \n", middle);
    			return middle;
    		 }
    	}
    	return -1;
    
    }
    
    
    int main(){
    	printf("start testing --- \n");
    	int res;
    
    	res = binarySearch(seq, len, target);
    
    }

###  ###

### 3. 插值查找算法 ###

折半查找采用下列 这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：

> mid=(low+high)/2, 即mid=low+1/2\*(high-low);

通过类比，我们可以将查找的点改进为如下：

> mid=low+(key-a\[low\])/(a\[high\]-a\[low\]) \* (high-low)，

也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

**基本思想：**基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

注：**对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。**

**运行发现，二分查找法需要 3 次**

**而自适应插值法 1 次就找到了**

#include <stdio.h>
    #include <stdlib.h>
    
    int target = 10;
    int unFind = 11;
    int array[] = { 2, 3, 4, 6, 8, 10, 12 };
    int seq[] = { 1, 2, 3, 5, 7, 9, 10, 12 };
    int testArray[] = { 1, 3, 2, 5, 9, 2, 4, 5 };  // 测试快速排序
    int len = sizeof(array) / sizeof(array[0]);
    
    // 顺序查找法
    int findBySeq(int *a, int len, int target){
    	for (int i = 0; i < len; i++){
    		if (a[i] == target){
    			return i;
    		}
    	}
    	printf("没有找到指定的数值-- \n");
    	return -1;
    }
    
    
    // 二分查找法
    int binarySearch(int *array, int len, int target){
    	int low = 0;
    	int high = len - 1;
    	int middle;
    	int count = 0;
    	while (low <= high){
    		middle = (low + high) / 2;
    		if (array[middle] < target){
    			low = middle + 1;
    			count++;
    		}else if (array[middle] > target){
    			high = middle - 1;
    			count++;
    		}else{
    			printf("找到数值,位置为 %d \n", middle);
    			count++;
    			printf("查找次数为 %d \n", count);
    			return middle;
    		 }
    	}
    	return -1;
    
    }
    
    // 插值查找法
    
    int insertSearch(int *array, int len, int target){
    	int low = 0;
    	int high = len - 1;
    	int middle;
    	int count = 0;
    	while (low <= high){
    		middle = low + (target - array[low]) / (array[high] - array[low]) * (high -low);
    		if (array[middle] < target){
    			low = middle + 1;
    			count++;
    		}
    		else if (array[middle] > target){
    			high = middle - 1;
    			count++;
    		}
    		else{
    			printf("找到数值,位置为 %d \n", middle);
    			count++;
    			printf("查找次数为 %d \n", count);
    			return middle;
    		}
    	}
    	return -1;
    
    }
    
    int cmp(const void* a, const void* b){
    	return (*(int *)a - *(int*)b);
    }
    
    
    int main(){
    	printf("start testing --- \n");
    	int res;
    
    	res = findBySeq(array, len, target);
    	printf("result is : %d \n", res);
    
    	/*
    	int length = sizeof(testArray) / sizeof(testArray[0]);
    	qsort(testArray, length, sizeof(testArray[0]), cmp);
    	for (int i = 0; i < length; i++){
    		printf(" %d - ", testArray[i]);
    	}
    	*/
    
    	res = binarySearch(seq, len, target);
    	printf("开始查找----\n");
    	res = insertSearch(seq, len, target);
    	printf("\n");
    	
    }

###  ###

### 4. 分块查找算法 ###

分块查找是折半查找和顺序查找的一种改进方法，**分块查找由于只要求索引表是有序的，对块内节点没有排序要求**，因此特别适合于节点动态变化的情况，其核心有二索引表，二是分块处理。

分块查找要求把一个大的线性表分解成若干块，**每块中的节点可以任意存放，但块与块之间必须排序**。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。

此外，还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，**对索引表的查找可以采用顺序查找或折半查找**；然后，**在相应的块中采用顺序查找**，即可找到对应的节点。

**例子：**

![3903.png][]

假设要查找关键字 38 的具体位置。首先将 38 依次和索引表中各最大关键字进行比较，因为 22 < 38 < 48，所以可以确定 38 如果存在，肯定在第二个子表中。

由于索引表中显示第二子表的起始位置在查找表的第 7 的位置上，所以从该位置开始进行顺序查找，一直查找到该子表最后一个关键字（一般将查找表进行等分，具体子表个数根据实际情况而定）。结果在第 10 的位置上确定该关键字即为所找。

#include <stdio.h>
    #include <stdlib.h>
      
    struct index 
    { 
    　　
    　　int key;  // 用于表示块结构大小
    　　int start; //块范围的起始值
      
    } newIndex[3];  //定义结构体数组
    
    
    int search(int key, int a[])
    {
    　　int i, startValue;
    　　i = 0;
    //分为3 个块
    　　while (i<3 && key > newIndex[i].key) 
    　　{ 
    　　　　// 确定在哪个块中，遍历每个块，确定key在哪个块中
    　　　　i++;
    　　}
    　　if (i>=3) 
    　　{ 
    　　　　//大于分得的块数，则返回0
    　　　　return -1;
    　　}
    　　startValue = newIndex[i].start; //startValue等于块范围的起始值
    　　while (startValue <= startValue+5 && a[startValue]!=key)
    　　{
    　　　　startValue++;
    　　}
    　　if (startValue>startValue+5) 
    　　{ 
    　　　　//如果大于块范围的结束值，则说明没有要查找的数
    　　　　return -1;
    　　}
      
    　　return startValue;
    }
    
    
    // 快速排序需要定义的函数 
    int cmp(const void *a,const void* b)
    {
    　　return (*(struct index*)a).key>(*(struct index*)b).key?1:-1;
    }
    
    
      
    int main()
    {
    　　int i, j=-1, k, key;
    　　int a[] = {33,42,44,38,24,48, 22,12,13,8,9,20, 60,58,74,49,86,53};
    　　//确认模块的起始值和最大值
    　　for (i=0; i<3; i++) 
    　　{
    　　　　newIndex[i].start = j+1; //确定每个块范围的起始值
    　　　　j += 6;
    　　　　for (int k=newIndex[i].start; k<=j; k++) 
    　　　　{
    　　　　　　if (newIndex[i].key<a[k]) 
    　　　　　　{
    　　　　　　　　newIndex[i].key = a[k];
    　　　　　　}
    　　　　}
    　　}
    　　//对结构体按照 key 值进行排序
    　　qsort(newIndex,3, sizeof(newIndex[0]), cmp);
    　　//输入要查询的数，并调用函数进行查找
    　　printf("请输入您想要查找的数：\n");
    　　scanf("%d", &key);
    　　k = search(key, a);
    　　//输出查找的结果
    　　if (k>0) 
    　　{
    　　　　printf("查找成功！您要找的数在数组中的位置是：%d\n",k+1);
    　　}
    　　else
    　　{
    　　　　printf("查找失败！您要找的数不在数组中。\n");
    　　}
      
    　　return 0;
    }

### 项目推荐： ###

**[2000多G的计算机各行业电子资源分享（持续更新）][2000_G]**

**[2020年微信小程序全栈项目之喵喵交友【附课件和源码】][2020]**

**[Spring Boot开发小而美的个人博客【附课件和源码】][Spring Boot]**

**[Java微服务实战296集大型视频-谷粒商城【附代码和课件】][Java_296_-]**

**[Java开发微服务畅购商城实战【全357集大项目】-附代码和课件][Java_357_-]**

**[最全最详细数据结构与算法视频-【附课件和源码】][-]**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]

[3903.png]: /images/20230209/9c95591b9a1d492bbeb243cc58a3a2d2.png
[2000_G]: https://mp.weixin.qq.com/s/sP4JgGWkCzpgwKr9sAV2_Q
[2020]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487704&idx=1&sn=5f4b2127c4d49fd07ae072a0721424a2&chksm=e8036fc2df74e6d489c4aa9b06f917ef7cee6027f13e150fca53cf79d5d188d4ccc1af49e098&scene=21#wechat_redirect
[Spring Boot]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487798&idx=2&sn=ac0293b996521b872a9dba5fbb3e65e6&chksm=e8036e2cdf74e73aba104a9a994a5b2e31483e8dcbe0f1d9936f6d5173b887e1560f59d2819c&scene=21#wechat_redirect
[Java_296_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487674&idx=1&sn=7aff0bdf2bb727303f3d3618995aef21&chksm=e8036fa0df74e6b6d872c7e6ece179c524ed463a4a6b74c96875475c9a3d5ddb903427dd993b&scene=21#wechat_redirect
[Java_357_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247486376&idx=1&sn=d1fef270c463ea8ac663f6fbfedd70a0&chksm=e80374b2df74fda4d3bafba878a106a19e18c5fcda266008f4f37975847a21bc612ffcd5ff39&scene=21#wechat_redirect
[-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487750&idx=1&sn=747bccbb5f5ea6b58915198de40da777&chksm=e8036e1cdf74e70ae97a5e8e265b49d7236d904d291203309159d07ba1724033062c0e370843&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/a76d688f9d8f45b3b6b3016d326da336.png