实验二 折半查找算法设计

实验二折半查找算法设计题目：折半查找算法设计问题描述：（1）分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。（2）编写程序实现：在保存于数组的10000个有序数据元素中查找数据元素x是否存在。数据元素x要包含两种情况：一种是数据元素x包含在数组中；另一种是数据元素x不包含在数组中（3）数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。（4）根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。基本要求：（1）10000个数据可以初始赋值时实现，也可以调用系统的随机函数，再设计一个排序函数实现。（2）两种方法时间效率的分析对比可以有两种方法，一种是理论分析方法，一种是实际记录运行时间。（3）提交实验报告。测试数据：运行算法时，当输入的数据小于10000，例如输入9999时，显示该数据在数组中，下标为9998，并且分别显示递归和循环结构下的时间；当输入的数据大于10000时，例如输入20000时，显示这个这个数据不再该数组中。算法思想：设有数组a中元素按从小到大的次序排列，a的下界下标为low，上界下标为high，首先计算出a的中间位置下标mid=（low+high)/2,1.递归算法思想：比较x和a[mid],若x=a[mid]，则查找成功；若xa[mid]，则随后调用算法自身在下标为low，上界下标为mid-1的区间继续查找；若xa[mid]，则随后调用算法自身在下标为mid+1，上界下标为high的区间继续查找。当查找区间小于等于0时，查找过程结束。2.循环结构思想：用while(low=high)控制循环，比较x和a[mid]，若x=a[mid]，则查找成功；若xa[mid]，则随后在下标为low，上界下标为mid-1的区间继续查找；若xa[mid]，则随后在下标为mid+1，上界下标为high的区间继续查找。当查找区间小于等于0时，查找过程结束。模块划分：1.头文件time.h中包含time()和difftime(end,start)函数，分别实现取系统当前时间和end减去start的时间差；2.头文件stdlib.h中包含rand()函数，实现随机数的生成；3.voidlist(inta[])实现对随机数从小到大的排序；4.intSearch(inta[],intlow,inthigh,intx)用递归算法实现折半查找数据元素的函数；5.intBSearch(inta[],intlow,inthigh,intx)用循环结构实现折半查找数据元素的函数；6.voidmain()主函数，测试用递归算法和循环结构实现折半查找数据元素的函数。数据结构：源程序：#includestdio.h#includetime.hintBsearch(inta[],intx,intlow,inthigh){intmid;if(lowhigh)return-1;mid=(low+high)/2;if(x==a[mid])returnmid;elseif(xa[mid])Bsearch(a,x,low,mid-1);elsereturnBsearch(a,x,mid+1,high);}intCsearch(inttest[],intx,intlow,inthigh){for(inti=0;ihigh;i=(low+high)/2){if(x==test[i])returni;elseif(xtest[i])low=i+1;elsehigh=i-1;}if(i=high)return-1;}voidmain(){time_tstart,end;doubledif;intBsearch(inta[],intx,intlow,inthigh);intCsearch(inttest[],intx,intlow,inthigh);inta[10000],x;intlow=0,high=10000,mid=0;printf(请输入要查找的元素：\n);scanf(%ld,&x);printf(x=%ld\n,x);for(inti=0;ihigh;i++)a[i]=i+1;intbn;time(&start);bn=Bsearch(a,x,0,10000);if(bn==-1)printf(x不在数组a中！\n);elseprintf(x在数组a中，下标为%d\n,bn);time(&end);dif=difftime(end,start);printf(递归折半方法耗时为：%f秒\n,dif);intflag;time(&start);flag=Csearch(a,x,0,10000);if(flag==-1)printf(x不在数组a中！\n);elseprintf(x在数组a中，下标为%ld\n,flag);time(&end);dif=difftime(end,start);printf(循环折半算法耗时为：%f秒\n,dif);}测试情况：测试结果分析：程序运行结果和人工模拟分析过程完全相同。说明程序设计正确。但是因为测试程序中数组中的元素过少不能体现出两种情况即递归和循环结构两种算法的时间差别。理论分析知循环结构的效率高于递归结构