算法设计与分析二分查找实验报告

课 程 设 计 说 明 书

设计题目： 二分查找程序的实现

专业： 班级：

设计人：

山 东 科 技 大 学 年 月 日

课 程 设 计 任 务 书

学院：信息科学与工程学院 专业： 班级： 姓名：

一、课程设计题目： 二分查找程序的实现 二、课程设计主要参考资料

（1） 计算机算法设计与分析（第三版）王晓东著 （2） 三、课程设计应解决的主要问题

（1） 二分查找程序的实现 （2） （3） 四、课程设计相关附件（如：图纸、软件等）：

（1） （2）

五、任务发出日期： 2013-11-21 课程设计完成日期： 2013-11-24

指导教师签字： 系主任签字 ：

指导教师对课程设计的评语

成绩：

指导教师签字：

年 月 日

二分查找程序的实现

一、 设计目的

算法设计与分析是计算机科学与技术专业的软件方向的必修课。同时，算法设计与分析既有较强的理论性，也有较强的实践性。算法设计与分析的实验过程需要完成课程学习过程各种算法的设计和实现，以达到提高教学效果，增强学生实践动手能力的目标。

用分治法，设计解决二分查找程序的实现问题的一个简捷的算法。通过解决二分查找程序的实现问题，初步学习分治策略。

二、 设计要求

给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。实现二分搜索的递归程序并进行跟踪分析其执行过程。

用顺序搜索方法时，逐个比较a[0:n-1]中的元素，直至找出元素x，或搜索遍整个数组后确定x不在其中。这个方法没有很好的利用n个元素已排好序这个条件，因此在最坏情况下，顺序搜索方法需要O(n)次比较。要求二分法的时间复杂度小于O(n)。

三、 设计说明 （一）、需求分析

二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用O(logn)时间完成搜索任务。

该算法的流程图如下：

开始bott=0,top=n-1bott<=topYmid=(bott+top)/2x==a[mid]N已找到未找到x

（二）、概要设计

二分查找的基本思路是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x，算法终止；如果xa[n/2]，则只要在数组a的右半部分继续搜索x。

由于二分查找的数组不一定是一个整数数组，所以我采用了C++中的模板函数，将排序函数Sort和二分查找函数BinarySort写为了模板函数，这样不尽可以查找整数数组，也可以查找小数数组。

由于查找的数组的长度不固定，所以我用了C语言中的malloc和realloc函数，首先定义一个数组指针，用malloc函数该它分配空间，然后向数组中存数，当数组空间满时，在用realloc函数为数组再次分配空间。由于在随机输入一组数时不知在什么位置停止，所以

在输入完一组数之后，按Ctrl+Z键结束输入，然后再用cin.clear()将输入恢复，再继续输入。

（三）、详细设计

#include #include #include using namespace std; #define N 10//初始空间大小 #define n 10//增加空间大小 template void sort(Type a[],int num){ double temp;

for(int i = 1;i <= num-1;i++){ for(int j = 0;j < num-i;j++){ if(a[j] > a[j+1]) {

temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } }

template

int BinarySearch(Type *a,Type x,int m){ int left=0; int right=m-1; while(left<=right){

int middle = (left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) left=middle+1; else

right=middle-1; } return -1; }

int main(){

int *a,num,length,i = 0; a = (int *)malloc(sizeof(int)*N);

cout<<\请输入一组数(Ctrl+z停止输入)\ while(cin>>a[i]){ i++;

if(i>=N){

a = (int *)realloc(a,sizeof(int)*(length+n)); length += n; } } sort(a,i);

for(int j = 0;j cout<

cout<<\请输入要查找的数：\ cin>>num;

if(BinarySearch(a,num,i)!=-1){

cout<

cout<

double *b,num1; int length1,i1 = 0;

b = (double *)malloc(sizeof(double)*N);

组

中

，

cout<<\请输入一组数\ while(cin>>b[i1]){ i1++; if(i1>=N){

b = (double *)realloc(a,sizeof(double)*(length1+n)); length1 += n; } } sort(b,i1);

for(int j = 0;j

cout<

cout<<\请输入要查找的数：\ cin>>num1;

if(BinarySearch(b,num1,i1)!=-1){

cout<

cout<

组

中

，

}

return 0;

四、运行结果及分析

运算结果：

分析：

很容易看出，每执行一次算法的while循环，待搜索数组的大小减小一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此，整个算法在最坏情况下的时间复杂性为O(logn)。

五、总结

通过这次试验，解决了二分查找问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只看是不够的还要动手分析一下，这样才能学好算法。

本文来源：https://www.bwwdw.com/article/27la.html