C语言--顺序查找、折半查找-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言--顺序查找、折半查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

顺序查找

实现逻辑

顺序查找（sequential search）就是按照数组的顺序一一比较数组中的元素的值和所查找的值。如下图表所示，遍历数组进行比较。若找到，则break跳出循环。

a[0]	a[1]	a[2]	a[3]	a[4]
9	12	22	13	34
22==9?
	22==12?
		22==22?

实现代码

#include<stdio.h>
int main(){

	int arr[5]={9,12,22,13,34};
	int i,x,n;
	n=0;	//数组下标记录
	printf("请输入查找元素x:");
	scanf("%d",&x);
	for(i=0; i<5; i++,n++)
		if(arr[i] == x){
			break;
		}
	if(n==5)
		printf("查找失败\n");
	else{
		printf("查找成功，为数组第%d位元素\n",n+1);
	}

	return 0;
}

运行结果

C语言--顺序查找、折半查找,C,c语言,算法,笔记,排序算法

折半查找

实现逻辑

折半搜索（英语：half-interval search），也称二分搜索、对数搜索。是一种在有序数组中查找某一特定元素的搜索算法。

折半搜索从数组的中间元素开始比较，若相等，则查找成功；若所查找的元素大于或小于中间元素，则与数组大于或小于中间元素的那一半数组元素的中间元素比较。若在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

例子：

int a[5]={9,10,11,12,13};
int max,min,mid,n=13;//n为搜索元素,a[min]到a[max]则是每轮搜索的范围（边界）。
max=4;min=0;

第一轮 mid=(min+max)/2=4/2=2;元素n和a[mid]比较，n大于a[mid],则去右半区进行比较。

缩小搜索区域min=mid+1=2+1=3;

第二轮 mid=(3+4)/2=3;元素n和a[mid]比较，n大于a[mid],则去右半区进行比较。

缩小搜索区域min=mid+1=3+1=4;

第三轮 mid=(4+4)/2=4;元素n和a[mid]比较，n等于a[mid],则break跳出循环。

a[0]	a[1]	a[2]	a[3]	a[4]
9	10	11	12	13
min		mid 13==11?		max
			min mid 13==12?	max
				min mid max 13==13?

实现代码

#include<stdio.h>
int main(){
	//max为数列长度，a[0]作为第一个数组元素
	int a[10]={0,1,2,3,4,5,6,7,8,9},min=0,max=9,mid,n; 
	printf("请输入您要查找的数据:");
	scanf("%d",&n);
	while(min <= max){
		mid = (min+max)/2;
		if(n>a[mid])	//若大于中间元素
			min = mid+1;
		else if(n<a[mid]){//若大于中间元素
			max = mid-1;
		}else{
		printf("输入的数在数列的第%d位\n",mid+1);
			break;
		}
	}

    if(min > max)
		printf("查找失败\n");
    
	return 0;
}