实验二-折半查找算法设计.doc

实验二 折半查找算法设计题目：折半查找算法设计问题描述：（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和amid,若x=amid，则查找成功；若xamid，则随后调用算法自身在下标为mid+1，上界下标为high的区间继续查找。当查找区间小于等于0时，查找过程结束。2.循环结构思想：用while(low = high)控制循环，比较x和amid，若x=amid，则查找成功；若xamid，则随后在下标为mid+1，上界下标为high的区间继续查找。当查找区间小于等于0时，查找过程结束。模块划分：1.头文件time.h中包含time()和difftime(end,start)函数，分别实现取系统当前时间和end减去start的时间差； 2.头文件stdlib.h中包含rand()函数，实现随机数的生成；3.void list(int a)实现对随机数从小到大的排序；4.int Search(int a,int low,int high,int x)用递归算法实现折半查找数据元素的函数；5.int BSearch(int a, int low, int high, int x)用循环结构实现折半查找数据元素的函数；6.void main()主函数，测试用递归算法和循环结构实现折半查找数据元素的函数。数据结构：源程序：#include#includeint Bsearch(int a,int x,int low,int high)int mid;if(lowhigh) return -1;mid=(low+high)/2;if(x=amid) return mid;else if(xamid)Bsearch(a,x,low,mid-1);elsereturn Bsearch(a,x,mid+1,high);int Csearch(int test,int x,int low,int high)for(int i=0;itesti) low=i+1;else high=i-1;if(i=high) return -1;void main()time_t start,end;double dif;int Bsearch(int a,int x,int low,int high);int Csearch(int test,int x,int low,int high);int a10000,x;int low=0,high=10000,mid=0;printf(请输入要查找的元素：n);scanf(%ld,&x);printf(x=%ldn,x);for(int i=0;ihigh;i+)ai=i+1;int bn; time(&start);bn=Bsearch(a,x,0,10000);if(bn=-1) printf(x不在数组a中 ！n);else printf(x在数组a中，下标为%dn,bn);time(&end);dif=difftime(end,start);printf(递归折半方法耗时为：%f秒n,dif); int flag; time(&start);flag=Csearch(a,x,0,10000);if(flag=-1) printf(x不在数组a中！n);else printf(x在数组a中，下标为%ldn,flag);time(&end); dif=difftime(end,start);printf(循环折半算法耗时为：%f秒n,dif); 测试