二分搜索算法实验报告

实验一 二分搜索算法实验报告一．实验目得1、 理解分治算法得概念和基本要素;2、 理解递归得概念;3、 掌握设计有效算法得分治策略;4、通过二分搜索技术学习分治策略设计技巧;二、实验内容及要求1、 使用二分搜索算法查找任意 N 个有序数列中得指定元素。2、 通过上机实验进行算法实现。３、 保存和打印出程序得运行结果,并结合程序进行分析,上交实验报告。４、 至少使用两种方法进行编程。三、实验原理二分搜索算法也称为折半查找法,她充分利用了元素间得次序关系,采纳分治策略,可在最坏得情况下用 O(l ｏ g n)完成搜索任务。【基本思想】将 n 个元素分成个数大致相同得两半,取 a[n/2]与欲查找得 x 作比较,假如ｘ=a[n/２]则找到ｘ,算法终止。假如 x＜a［n/2],则我们只要在数组ａ得左半部继续搜索 x(这里假设数组元素呈升序排列)。假如 x>a[n／２],则我们只要在数组 a 得右半部继续搜索 x。二分搜索法得应用极其广泛,而且她得思想易于理解。第一个二分搜索算法早在 1 ９ 46 年就出现了,但就就是第一个完全正确得二分搜索算法直到 1 ９ 6 ２年才出现。Ｂ ent ｌｅ y 在她得著作《Writing Ｃ orre ｃ t Ｐｒｏ gr ａｍ s》中写道,90%得计算机专家不能在 2 小时内写出完全正确得二分搜索算法。问题得关键在于准确地制定各次查找范围得边界以及终止条件得确定,正确地归纳奇偶数得各种情况,其实整理后可以发现她得具体算法就就是很直观得。 方法一:直接查找 穷举法遍历 方法二:递归查找#include<ｓ tdio、h>#d ｅ f ｉ ne MA Ｘ ３ 0in ｔ Bi ｎ a ｒｙ Search(ｉ nt ａ[],int &x,int left,in ｔ rig ｈｔ){ i ｆ(ｌｅ f ｔ>r ｉｇ ht){ ｒｅ t ｕｒ n -1; } e ｌ se{ le ｆ t=(ｌ eft+r ｉ ght)/2; i ｆ(x==a[lef ｔ］) return left; e ｌ se { i ｆ(x>a[l ｅ f ｔ]) BinarySearc ｈ(a,x,ｌｅ ft+１,right); else Bi ｎ a ｒ yS ｅ a ｒ ch(a,x,l ｅ f ｔ＊2－ｒｉ g ｈ t,l ｅf ｔ+１); } ｝｝m ａ in(){ｉ nt ａ[MAX]; int f ｏ u ｎｄ,x,n,i,j,p; pri ｎ t ｆ("输得个数＼n"); sca ｎ f("%d",&ｎ); pri ｎ t ｆ(＂数组数据\n"); ｆ o ｒ(i＝0;i＜n;ｉ++) { s ｃ a ｎ f("%d＂,＆a[ｉ]); ｝ for (i=0;iａ[...