C语言编程九种必会查找算法附完整代码 [复制链接]

算法思路：

确定查找范围low=0，high=N-1，计算中项mid=（low+high）/2。

若mid==x或low=high,则结束查找；否则，向下继续。

若amidx,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给low，并重新计算mid，转去执行步骤2；若midx，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给higt，并重新计算mid，转去执行步骤2。

说明：

查找元素必须是有序的，如果是无序的则要先进行排序操作。

在做查找的过程中，如果low指针和high指针的中间位置在计算时位于两个关键字中间，即求得mid的位置不是整数，需要统一做取整操作。

折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

——《大话数据结构》

代码：

#includestdio.h#includestdlib.h#definekeyTypeinttypedefstruct{　　keyTypekey;//查找表中每个数据元素的值}ElemType;typedefstruct{　　ElemType*elem;//存放查找表中数据元素的数组　　intlength;//记录查找表中数据的总数量}SSTable;//创建查询数据voidCreate(SSTable**st,intlength){　　(*st)=(SSTable*)malloc(sizeof(SSTable));　　(*st)-length=length;　　(*st)-elem=(ElemType*)malloc((length+1)*sizeof(ElemType));　　printf("输入表中的数据元素：\n");　　//根据查找表中数据元素的总长度，在存储时，从数组下标为1的空间开始存储数据　　for(inti=1;i=length;i++)　　{　　　　scanf("%d",((*st)-elem.key));　　}}//折半查找函数key为要查找的元素intSearch_Bin(SSTable*str,keyTypekey){　　intlow=1;//初始状态low指针指向第一个关键字　　inthigh=str-length;//high指向最后一个关键字　　intmid;　　while(low=high)　　{　　　　mid=(low+high)/2;//int本身为整形，所以，mid每次为取整的整数　　　　if(str-elem[mid].key==key)//如果mid指向的同要查找的相等，返回mid所指向的位置　　　　{　　　　　　returnmid;　　　　}elseif(str-elem[mid].keykey)//如果mid指向的关键字较大，则更新high指针的位置　　　　{　　　　　　high=mid-1;　　　　}　　　　//反之，则更新low指针的位置　　　　else　　　　{　　　　　　low=mid+1;　　　　}　　}　　return0;}intmain(){　　SSTable*str;　　intnum;　　printf("请输入创建数据元素的个数：\n");　　scanf("%d",num);　　Create(str,num);　　getchar();　　printf("请输入要查找的数据：\n");　　intkey;　　scanf("%d",key);　　intlocation=Search_Bin(str,key);　　if(location==0){　　　　printf("没有查找到");　　}else{　　　　printf("要查找的%d的顺序为：%d",key,location);　　}　　return0;}

运行结果：