项 目 名 称：各种查找算法的性能测试项目成员：组编号：完成时间： 目录前言.2正文.2第1章 简介.2 1.1顺序查找问题描述.2 1.2二分查找问题描述.2 第2章 算法定义.22.1顺序查找算法定义.2 2.2二分查找算法定义.3 第3章 测试结果（Testing Results).5 3.1 实验结果表 .5 3.2 散点图记录 .5第4章 分析和讨论.6 4.1顺序查找分析.6 4.2二分查找分析.6附录：源代码（基于C语言的).7声明 .13前言查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。 对于查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。查找问题没有稳定性的问题，但会发生其他的问题（动态查找表）。在数据结构课程中，我们已经学过了几种查找算法，比较有代表性的有顺序查找（蛮力查找），二分查找 （采用分治技术），哈希查找（理论上来讲是最好的查找方法）。第一章：简介（Introduction）1.1顺序查找问题描述：顺序查找从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。1.2二分查找问题描述：（1）分析掌握折半查找算法思想，在此基础上，设计出递归算法和循 环结构两种实现方法的折半查找函数。（2）编写程序实现：在保存于数组ai有序数据元素中查找数据元素k是否存在。数元素k要包含两种情况：一种是数据元素k包含在数组中；另一种是数据元素k不包含在数组中（3）数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。（4）根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。第二章：算法定义（Algorithm Specification）2.1顺序查找从表的一端向另一端逐个进行记录的关键字和给定值（要查找的元素）的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查找记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。顺序查找的算法如下：int SeqSearch1(int r , int n, int k) /数组r1 rn存放查找集合，n是数组中元素的个数（即查找表的长度），k是要查找的元素 i=n;/从后往前把表中的元素与要查找的元素进行比较 while (i0 & ri!=k)/当i0并且数组元素中的值不等于要查找元素时，i减一继续执行while循环 i-; return i;/i的值为0则没找到，为非0则i为要查找元素的位置 2.2二分查找二分查找又称折半查找，二分查找首先要求待查找的表是有序表，如果要查找的元素是表的中间的那个元素，则找到要查找的元素，查找成功；如果要查找的元素比中间的那个元素小则使用相同的策略只在左边的区间查找就可以；如果要查找的元素比中间的那个元素大，则使用相同的策略在右边的区间进行查找；每次将待查找的元素的所在区间缩小一半。（1）二分查找算法的递归算法int binary_search_2(int a,int n,int k)/递归的二分查找算法的伪代码：查找表放在数组a中，n是查找表中元素的个数，k是待查找的元素 int Low,Mid,High;Low=0,High=n-1;/选择查找的最大的范围 Mid=(Low+High)/2; /quicksort(a,0,SIZE-1);if (Low=High) return -1;/数字-1表示没有结果 if (aMid=k) return Mid; /找到要查找的元素 else if (aMidk) return (binary_search_2(a,Mid-1,k);/需要在左边的更小的范围内查找 else return (binary_search_2(a+Mid+1,High-Mid,k);/在右边的更大的范围内查找 （2）二分查找的非递归算法int binary_search_1(int a,int n,int k) /非递归的二分查找算法的伪代码：查找表放在数组a中，n是查找表中元素的个数，k是待查找的元素 int Low,High,i,mid; Low=0; High=n-1; while(Lowamid)Low=mid+1;/在后半区间查找else High=mid-1;/在前半区间查找return 0;/查找失败第3章 ：测试结果（Testing Results）3.1实验结果表： 查找算法随机数组元素个数（个）查找时间（seconds） 顺序查找20.02200040.04700060.062000 80.082000 100.100000 二分查找 20.19000040.39000060.39000080.060000100.060000 3.2散点图：注释：横轴为数组元素个数，纵轴为(查找时间/1000)。 第四章：分析和讨论4.1.实现顺序查找算法：（1）顺序查找算法思路很简单，就是一种遍历的思想，一个个查找目标元素，实现也很简单。（2）对于有n个元素的表适用顺序查找。比较次数：不成功：比较n次。成功查找：最好的情况为1次，即第一个元素即为目标元素；最差的情况为n次；平均比较次数（n+1）/2次。所以当表很大时，顺序查找的代价是很大的。（3）顺序查找算法不会有重复的比较出现，即一旦找到即成功，但同时这种代价是当表中有重复的目标元素时（比如有多个目标元素）我们只能得到第一个元素的位置。顺序查找算法时间复杂度为O(n)。4.2实现二分查找算法：（1）二分查找法思路：递增排列的表，首先从中间元素开始查找，如果元素比目标元素小，则查找后半部分表，反之查找前半部分表，并重复这一过程。这样每次查找中我们都把表的长度减半。（2）二分查找在实现中有量Low和High，每次减半的过程体现在Low和High的改变上，在代码的实现上可以使用单纯的循环或者用函数递归的思想。递归思想更容易理解，但编写之后我们发现函数是尾递归，尾递归通常可以用简单的循环实现，循环在操作来说没有了函数调用的过程，更节省时间和空间。（3）