C语言数据结构之查找（顺序查找，折半查找）

电玩女神 2022-12-02 04:09 252阅读 0赞

## C语言数据结构之查找（顺序查找，折半查找） ##

tips：前些天已经学习了树和图的相关知识，今天来总结下两种常用的查找方式（顺序查找，折半查找）。

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

为了演示方便，顺序查找和折半查找的数据存储结构就直接采用数组。

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

**1、顺序查找**

**顺序查找又称线性查找，主要用于在线性表中进行查找；**  
顺序查找跟我们用循环遍历进行暴力破解类似。。

直接看代码：

#define N 11
    
    //顺序查找（适用于线性表）
    int Seq_Search(int *arr, int key) 
    {
        
    	int i;
    	arr[0] = key;//0号下标作为哨兵
    	for (i = N-1; arr[i] != key; i--);
    	return i;
    }

对，顺序查找就是这么简单。。。

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

**2、折半查找（二分查找）**

**折半查找仅适用于有序的顺序表**

思路：

*  将给定值key与中间元素的关键字对比；
 *  若相等，则直接返回该元素的位置；
 *  若不等，则在前半部分或者后半部分进行查找；

具体实现：

//折半查找（二分查找），适用于有序的顺序表
    int Binary_Search(int *arr, int key)
    {
        
    	int low = 1;//元素起始下标
    	int high = N-1;//最后元素下标
    	int mid;//中间元素下标
    
    	while (low <= high)
    	{
        
    		mid = (low + high) / 2;
    		if (arr[mid] == key)
    			return mid;//查找成功
    		else if (arr[mid] > key)
    			high = mid - 1;//查找前半部分
    		else
    			low = mid + 1;//查找后半部分
    	}
    	return -1;//查找失败
    }

**注意这里循环的终止条件是low<=high;**

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

接下来，我们可以在main()函数中测试一下：

int main()
    {
        
    	//数组的0号下标不存放实际意义key（可以声明时存放数组长度）
    	int arr1[N] = {
         N,1,4,2,7,5,6,9,8,3,0 };
    	if (Seq_Search(arr1, 4) != 0)
    		printf("4元素下标为：%d\n", Seq_Search(arr1, 4));
    	else
    		printf("该元素不存在！\n");
    
    
    	int arr2[N] = {
         N,0,1,2,3,4,5,6,7,8,9 };
    	if (Binary_Search(arr2, 4) != -1)
    		printf("4元素下标为：%d\n", Binary_Search(arr2, 4));
    	else
    		printf("该元素不存在！\n");
    
    	return 0;
    }

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]

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

积一时之跬步，臻千里之遥程。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/df0aed593b9244e9a3d1b473e597da3d.png