C语言笔记：数组元素查找

偏执的太偏执、 2023-06-07 08:09 14阅读 0赞

### 文章目录 ###

*  常规查找法（顺序查找）
 *  折半查找法（二分查找）
 *   *  算法描述
     *  实现代码

# 常规查找法（顺序查找） #

顺序查找是按照一定顺序将各个数据与待查数据进行比较，看是否有与要查找的数据相等的数据，查找的结果有两种：查找成功与查找失败

#include <stdio.h>
    #define N 10
    void Input(int a[],int n);//杈撳叆鏁扮粍鐨刵涓厓绱?
    int Search(int a[],int n,int x);
    int main(void)
    { 
    	int a[N];
    	printf("输入数组a的%d个元素：\n",N);
    	Input(a,N);
    	printf("请输入要查找的元素x：");
    	int x;
    	scanf("%d",&x);//输入要查找的元素x
    	int res=Search(a,N,x);
    	if(res!=-1)
    	{ 
    		printf("查找%d成功，它的序号为：%d\n",x,res);
    	}
    	else
    	{ 
    		printf("查找%d失败\n");
    	}
    	return 0;
    }
    void Input(int a[],int n)
    { 
    	int i;
    	for(int i=0;i<n;i++)
    	{ 
    		scanf("%d",&a[i]);
    	}
    }
    int Search(int a[],int n,int x)
    { 
    	int i=0;
    	while(i<n)
    	{ 
    		if(a[i]==x)
    		{ 
    			break;
    		}
    		i++;
    	}
    	if(i<n)
    	{ 
    		return i+1;//鏌ユ壘鎴愬姛锛岃繑鍥炲叾搴忓垪鍙凤紙浠?寮€濮嬶級
    	}
    	return -1;
    }

输出：  
![在这里插入图片描述][20191013192238673.png]

# 折半查找法（二分查找） #

前面的顺序查找法对于任何一组数据均可使用，缺点就是需要和所有元素比较，当数据较多时效率很低。  
折半查找法的前提首先要求查找数据中的n个元素必须是有序的（假设是升序排列），如数据是无序的，则要先利用排序算法进行排序。

## 算法描述 ##

假设要查找的元素为x，查找范围的第一个元素的下标为low，最后元素的下标为high，如果要查找范围中至少有一个元素（即low<=high），则中间元素的下标为mid=(low+high)/2，比较x与mid对应元素的关系，如果x等于a\[mid\]则查询成功，返回mid+1；如果x小于a\[mid\]，若该数据中存在与x对应的元素，则其下标肯定在low~mid-1之间（执行high=mid-1）；如果x大于a\[mid\]，若该数据中存在与x对应的元素，则其下标肯定在mid+1与high之间（执行low=mid+1），重复折叠、查找。直到x==a\[mid\]为真或查找范围内没有元素（low<=high为假）

## 实现代码 ##

#include <stdio.h>
    #define N 6//数组元素个数 
    void Input(int a[],int n);//输入数组的n个元素
    void Output(int a[],int n);//输出数组的n个元素
    void BubbleSort(int a[],int n);//对有n个元素的数组进行冒泡排序
    int BinSearch(int a[],int n,int x);//在数组a中使用折半查找法查找x 
    void Swap(int *pa , int *pb);
    int main(void)
    { 
    	int a[N],x;
    	printf("请输入数组的%d个元素：\n",N);
    	Input(a,N);
    	BubbleSort(a,N);
    	printf("排序后的数组a的元素为：\n");
    	Output(a,N);
    	printf("输入要查找的元素x：");
    	scanf("%d",&x);
    	int t=BinSearch(a,N,x);//用折半查找法查找x
    	if(t!=0)
    	{ 
    		printf("查找%d成功，序号为%d\n",x,t);	
    	}
    	else
    	{ 
    		printf("查找%d失败！\n",x);
    	}
    	return 0;	
    } 
    void Input(int a[],int n)
    { 
    	for(int i=0;i<n;i++)
    	{ 
    		scanf("%d",&a[i]);
    	}
    }
    void Output(int a[],int n)
    { 
    	for(int i=0;i<n;i++)
    	{ 
    		printf("%-4d",a[i]);
    	}
    	printf("\n");
    }
    void BubbleSort(int a[],int n)
    { 
    	for(int i=1;i<n;i++)//轮数 
    	{ 
    		for(int j=0;j<=n-1-i;j++)
    		{ 
    			if(a[j]>a[j+1])
    			{ 
    				Swap(&a[j],&a[j+1]); 
    			}
    		}
    	} 
    }
    int BinSearch(int a[],int n,int x)
    { 
    	int low,high,mid;
    	low=0;high=n-1;
    	while(low<=high)//查找条件是区间中至少有一个元素
    	{ 
    		mid=(low+high)/2;//计算查找区间中间元素的下标
    		if(x==a[mid])
    		{ 
    			return mid+1;//mid对应的元素正好为要查找的元素，返回下标 
    		} 
    		else if(x<a[mid])
    		{ 
    			high=mid-1;//比中间元素小，则需要在左区间继续查找 
    		}
    		else
    		{ 
    			low=mid+1;//比中间元素大，则需要在右区间继续查找 
    		}
    	} 
    }
    void Swap(int *pa , int *pb)
    { 
    	int temp;
    	temp=*pa;
    	*pa=*pb;
    	*pb=temp; 
    }

输出：

![在这里插入图片描述][20191013201854667.png]

[20191013192238673.png]: /images/20230601/4a0c500b1d984842a9ccef8250e4b27d.png
[20191013201854667.png]: /images/20230601/466861c4fe2548799877529a10574a04.png