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

PAGE PAGE 1 / 4 实验二 折半查找算法设计 题目：折半查找算法设计 问题描述：（1）分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。 ）编写程序实现： 在保存于数组的 10000 个有序数据元素中查找数据元素 x 是否存在。数据元素 x 要包含两种情况：一种是数据元素 x包含在数组中；另一种是数据元素 x 不包含在数组中 ）数组中数据元素的有序化既可以初始赋值时实现， 也可以设计一个排序函数实现。 ）根据两种方法的实际运行时间， 进行两种方法时间效率的分析对 比。 基本要求：（1）10000 个数据可以初始赋值时实现， 也可以调用系统的随机函数， 再设计一个排序函数实现。 ）两种方法时间效率的分析对比可以有两种方法， 一种是理论分析方法，一种是实际记录运行时间。 提交实验报告。 测试数据：运行算法时，当输入的数据小于 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.void list(int a[]) 实现对随机数从小到大的排序； int Search(int a[],int low,int high,int x) 用递归算法实现折半查找数据元素的函数； int BSearch(int a[], int low, int high, int x) 用循环结构实现折半查找数据元素的函数； void main()主函数，测试用递归算法和循环结构实现折半查找数据元素的函数。 数据结构： 源程序： #includestdio.h #includetime.h int Bsearch(int a[],int x,int low,int high) { int mid; if(lowhigh) return -1; mid=(low+high)/2; if(x==a[mid]) return mid; else if(xa[mid]) Bsearch(a,x,low,mid-1); else }  return Bsearch(a,x,mid+1,high); int Csearch(int test[],int x,int low,int high) { for(int i=0;ihigh;i=(low+high)/2) { if(x==test[i]) return i; else if(xtest[i]) 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 a[10000],x; int low=0,high=10000,mid=0; printf( 请输入要查找的元素： \n); scanf(%ld,x); printf(x=%ld\n,x); for(int i=0;ihigh;i++) a[i]=i+1; int bn; time(start); bn=Bsearch(a,x,0,1