算法分析与设计实验报告

2024-01-13 10:03| 来源: 网络整理| 查看: 265

算法分析与设计实验报告——二分搜索算法的实现

目录：算法分析与设计实验报告——二分搜索算法的实现一、实验目的二、实验要求三、实验原理四、实验过程(步骤)五、运行结果六、实验分析与讨论七、实验特色与心得附件一实验过程(步骤)附件二运行结果

一、实验目的

掌握分治法的基本思想，建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。

二、实验要求

用c++语言实现二分搜索算法，分析时间复杂性。实现二分搜索的递归与非递归程序，并进行跟踪分析其执行过程，体会两者的执行效率。

三、实验原理

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。

四、实验过程(步骤)

见附件一实验步骤、特点重要源代码（流操作的部分要醒目的提示并注释）

五、运行结果

见附件二

六、实验分析与讨论

编写程序时由于传参错误，导致结果不能输出，一直输出没有找到，然后更改了参数之后，程序输出就正确了。还有数组的大小计算不能用strlen函数，要用sizeof（a）/sizeof（a[0]）。遇到的问题，及解决方案

七、实验特色与心得

这是我第一次实质上应用分治法编写程序。二分搜索算法能够实现O（logn）的时间复杂度，比一般的顺序搜索快了不少。这次实验也加深了我对分治法的理解。

附件一实验过程(步骤)

二分搜索的递归程序：

#include using namespace std; template int BinarySearch2(Type a[],const Type &x,int left,int right) //递归算法 { int middle=(left+right)/2; if(x==a[middle])//查找成功，返回下标 { return middle; } if(left>=right) { return -1; } else if(x>a[middle])//如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x { return BinarySearch2(a,x,middle+1,right); } else if(x int x,len,b1,b2; int a[]= {1,2,3,4,5,6,7,8,9,10};//初始化a数组 len=sizeof (a) / sizeof (a[0]);//计算a数组的长度 coutx; b2=BinarySearch2(a,x,0,len); if(b2==-1) cout int middle = (left+right)/2; if(x == a[middle])//查找成功，返回下标 return middle; if(x > a[middle])//如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x left = middle + 1; else//如果x1,2,3,4,5,6,7,8,9,10};//初始化a数组 len=sizeof (a) / sizeof (a[0]);//计算a数组的长度 coutx; b1=BinarySearch1(a,x,len); if(b1==-1) cout

【本文地址】

公司简介

联系我们