二分搜索算法实验报告

实验一二分搜索算法实验报告实验目的1、理解分治算法的概念和基本要素；2、理解递归的概念；3、掌握设计有效算法的分治策略；4、通过二分搜索技术学习分治策略设计技巧；实验内容及要求使用二分搜索算法查找任总N个有序数列中的指定元素。通过上机实验进行•算法实现。保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。4-至少使用两种方法进行编程。二・实验原理二分搜索算法也称为折半査找法，它充分利用了元素间的次序关系，采用分治第略，可在最坏的情况下用Odogn）完成搜索任务。【基本思想】将n个元素分成个数人致相同的两半，取a[M2]与欲査找的X作比较，如果x=arn/2]则找到x,算法终止。如果x<arn/2],则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索也二分搜索法的应用极其广泛，而且它的思想易于理解。第•个二分搜索算法早在1916年就出现了，但是第•个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作WritingCorrectPrograms》中写道，潞的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次査找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。方法一：直接查找穷举法遍历方法二：递归查找^include<stdio.h>^defineMAX30intBinarySearch(inta[],int&intleft,intright){if(left>right){returnT;}else{left=(left+right)/2：if(x==alleft])returnleft:else{if(x>a[left])BinarySearch(a,x,le£t+l,right):elseBinarySearch(a,x,le£t*2~right,left+1):}}}main(){inta：MAXj：intfound,x,n,i,j,p：printf(*输的个数\n"):scanf(飞d",&n):printf("数组数据\n"):for(i=0;i<n：i++){seanf(飞Sali]):}for(i=0：i<n_l：i++)p=i:for(j=i+l:j<n:j++)if(alp]>alj])P=J：if(p!=j)>：=aIp]:a[p]=a[i]:a[i]=x:}}for(i=0;i<n：i++){printf,a[i]);}printf("输入要査找的数\n");scan£&x):found=BinarySearch(a,x,0,n):if(found==~l){printf(*未找到\rT>:}else{printf("要査找的数在第%d个\n",found-1):}}方法三：迭代查找^include<stdio.h>#defineMAX30intBinarySearch(inta[],intintn){intleft=0:intright=n~l:intmiddle:while(left<=right){middle=(le£t+right)/2;if(x==aImiddle])returnmiddle;if(x>a[middlej)left=m£ddle^l:elserigh*=middle-l:}re*urn-l:}main()inta：MAXj:intfound,x,n,i,j,p：printfC数的个数\n"):scanf&n):printfC数组数据\n"):for(i=0:i<n;i++){seanf4a[i]):}for(i=0:i<n_l:i++)P=i：for(j=i+l:j<n;j++)if(aIp]>a[j])P=j：if(p!=j){x=a[p]:alp]=ali]:a[i]=x:}}for(i=0:i<n;i++){printf(*%d”,a[i]):}printfC输入要査找的数\n"):scanf&x):found=BinarySearch(a,x,n):if(found==~l){printf("未找到:printf("要査找的数在第个\tT,found^l):四•程序代码变量定义说明：BinarySmarch()算法：a-＞数组key・＞要査找的元素left-〉左标志right-）右标志（n-＞数据个数）MainO主函数:ound-》是否找到标志，-1衣示未找到，找到其值为下标要査找的元素旷＞元素个数i，j,P-〉循环控制变量（1）、递归查找^include<stdio.h>^defineMAX30intBinarySearch(inta[],intkey,intleft,intright){intmid=(right-right)/2+left:if(almidj==key){returnmid:}if(left>=right){returnT:}elseif(key>aImidj){returnBinarySearch(a,key,mid+1,right):}elseif(key<aImidj){returnBinarySearch(a,key,left,mid~l):}returnT:}intmain(void){inta：MAXj:intfound,x,n,i,j,p:printfC数据个数:”)：scanprintfC输入数据:\n"):for(i=0：i<n：i++){printW请输入第岗个数据二i)：seanf(^,&a[i])：}for(i=0:i<n-1:i++)〃选择排序{P=i：for(j=i+l;j<n:j++)if(a[p]>a[j])P巧；if(P!=j){x=a[p]:alp]=a[i]:ali]=x:}}printfCtll-Jf后的数据如下：”):for(i=0：i<n：i++){printfa[i]);}print£("\“")：printfC输入要査找的数:"):scanx);intleft=O,right=n:found=BinarySearch(a,x,left,right):if(found==~l){printf(*未找到\n"):}else{primf("要ft找的数在第%d个\n",found+1):}}(2)、非递归查找^include<stdio.h>^defineMAX30intBinarySearch(inta[],intkey,intlen){intmid=len/2:if(key==aImidj){returnmid:}intleft=0;intright=len~l:while(left<=right){"迭代查找mid=(right+left)/2:if(key<almid]){right=mid-l:}elseif(key>a[mid]){

left=rnid-?-l:}else{returnmid:}}returnT;}intmain(void){inta：MAXj:intfound,x,n,i,j,p:printfr数据个数:”)：scan£(飞d",&n):printfC输入数据::for(i=0：i<n;i++){printfC请输入第%d个数据:",i)；seanfCW,&a[i]):p=l:for(j=i+l：j<n:j++)if(a[p]>a[j])p=j:if(p!=j){x=a[p];a[p]=a[i]:a：ij=x：}}printf("排序后的数据如下:w):for(i=0:i<n：i++){printf,a[i]):}printf<*\n*):printfL输入要査找的数:”〉：scanf&x)：intleft=0,right=n:found=BinarySearch(a,x,n):if(found==~l){printf("未找到\n*>:}else{printf("耍査找的数在第鴛d个\n*,found+l):}}五.结果运行与分析找到要査找的数据：■LAU8«，'BDA0KUintnf«\•f-re*TwipVKftfi*jttf1illIfK:6也人请输人第叶故据:制hir：ji：:谕輛人笫.i—jftIRiHlllrI9XtHE卜■舅羽66埸柳人WPH4川取：制爪比•：‘：一未找到要查找的数据:■-SlhrhgnjmrrrtWzrA：G对任妆p:iSVi人兀1个右戈帐：3ifi^；谢输人斤•:力於JiCul.b“・U•j.iltJWIWi12zy•11A典•>IW[:IJy狛LE123143«69输几“卄期潮叶：七；•*F1•••・・』・••六•心得与体会通过这次实验，巩固了自己对二分搜索算法的理解，它是分治法的一个特殊例子，由此也对分治法有了更深一层次的认识。分而治之，化复杂为简单，不只是在算法中，在口常生活中也是极其重要的。正如Bentl