第三章：测试结果（Testing Results）
3.1实验结果表：
查找算法 随机数组元素个数（个） 2 4 6 8 10 二分查找 2 4 6 8 10 3.2散点图：
查找时间（seconds） 0.022000 0.047000 0.062000 0.082000 0.100000 0.190000 0.390000 0.390000 0.060000 0.060000 顺序查找
注释：横轴为数组元素个数，纵轴为(查找时间/1000)。
第四章：分析和讨论
4.1.实现顺序查找算法：
（1）顺序查找算法思路很简单，就是一种遍历的思想，一个个查找目标元素，实现也很简单。 （2）对于有n个元素的表适用顺序查找。比较次数：不成功：比较n次。成功查找：最好的情况为1次，即第一个元素即为目标元素；最差的情况为n次；平均比较次数（n+1）/2次。 所
以
当
表
很
大
时
，
顺
序
查
找
的
代
价
是
很
大
的
。
（3）顺序查找算法不会有重复的比较出现，即一旦找到即成功，但同时这种代价是当表中有重复的目标元素时（比如有多个目标元素）我们只能得到第一个元素的位置。 顺序查找算法时间复杂度为O(n)。 4.2实现二分查找算法：
（1）二分查找法思路：递增排列的表，首先从中间元素开始查找，如果元素比目标元素小，则查找后半部分表，反之查找前半部分表，并重复这一过程。这样每次查找中我们都把表的长度减半。 （2）二分查找在实现中有量Low和High，每次减半的过程体现在Low和High的改变上，在代码的实现上可以使用单纯的循环或者用函数递归的思想。 递归思想更容易理解，但编写之后我们发现函数是尾递归，尾递归通常可以用简单的循环实现，循环在操作来说没有了函数调用的过程，更节省时间和空间。 （3）编码中小小地方的改动可能对程序有很大的改观。
如上述两种二分查找非递归binary_search_1（不比较等于的情况）递归binary_search_2（添加等于情况）
折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
时间复杂度：二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(lgn)或O(n)。（n代表集合中元素的个数）
空间复杂度：虽以递归形式定义，但是尾递归，可改写为循环,所以空间复杂度为 O(n)=O(lgn)。
附录：源代码（基于C语言的）
#include \#include \#include \
#define SIZE 1000//待排数的规模
#define PRT_RT 1//是否显示排序前后的数组情况，对较大规模的数组不显示 //0为不显示，1为显示
//顺序查找算法
int SeqSearch1(int r[ ], int n, int k) //数组r[1] ~ r[n]存放查找集合，n是数组中元素的个数（即查找表的长度），k是要查找的元素 {
int i=n;//从后往前把表中的元素与要查找的元素进行比较
while(i>0 && r[i]!=k)
{
i--;
}
return i;//i的值为0则没找到，为非0则i为要查找元素的位置
}
//二分查找的递归算法
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;
if (Low>=High) return -1;//数字-1表示没有结果
if (a[Mid]==k) return Mid; //找到要查找的元素 }
//二分查找的非递归算法
int binary_search_1(int a[],int n,int k) {
int Low,High,i,mid; else if (a[Mid]>k)
return (binary_search_2(a,Mid-1,k));//需要在左边的更小的范围内查找
else return (binary_search_2(a+Mid+1,High-Mid,k));//在右边的更大的范围内查找
Low=0; High=n-1; while(Low {
