二分搜索算法實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)一二分搜索算法實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康?、理解分治算法的概念和基本要素；2、理解遞歸的概念；3、掌握設(shè)計(jì)有效算法的分治策略；4、通過二分搜索技術(shù)學(xué)習(xí)分治策略設(shè)計(jì)技巧；實(shí)驗(yàn)內(nèi)容及要求使用二分搜索算法查找任總N個(gè)有序數(shù)列中的指定元素。通過上機(jī)實(shí)驗(yàn)進(jìn)行?算法實(shí)現(xiàn)。保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析，上交實(shí)驗(yàn)報(bào)告。4-至少使用兩種方法進(jìn)行編程。二?實(shí)驗(yàn)原理二分搜索算法也稱為折半査找法，它充分利用了元素間的次序關(guān)系，采用分治第略，可在最壞的情況下用Odogn）完成搜索任務(wù)。【基本思想】將n個(gè)元素分成個(gè)數(shù)人致相同的兩半，取a[M2]與欲査找的X作比較，如果x=arn/2]則找到x,算法終止。如果x<arn/2],則我們只要在數(shù)組a的左半部繼續(xù)搜索x（這里假設(shè)數(shù)組元素呈升序排列）。如果x>a[n/2]，則我們只要在數(shù)組a的右半部繼續(xù)搜索也二分搜索法的應(yīng)用極其廣泛，而且它的思想易于理解。第?個(gè)二分搜索算法早在1916年就出現(xiàn)了，但是第?個(gè)完全正確的二分搜索算法直到1962年才出現(xiàn)。Bentley在他的著作WritingCorrectPrograms》中寫道，潞的計(jì)算機(jī)專家不能在2小時(shí)內(nèi)寫出完全正確的二分搜索算法。問題的關(guān)鍵在于準(zhǔn)確地制定各次査找范圍的邊界以及終止條件的確定，正確地歸納奇偶數(shù)的各種情況，其實(shí)整理后可以發(fā)現(xiàn)它的具體算法是很直觀的。方法一：直接查找窮舉法遍歷方法二：遞歸查找^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(*輸?shù)膫€(gè)數(shù)\n"):scanf(飛d",&n):printf("數(shù)組數(shù)據(jù)\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("輸入要査找的數(shù)\n");scan￡&x):found=BinarySearch(a,x,0,n):if(found==~l){printf(*未找到\rT>:}else{printf("要査找的數(shù)在第%d個(gè)\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數(shù)的個(gè)數(shù)\n"):scanf&n):printfC數(shù)組數(shù)據(jù)\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輸入要査找的數(shù)\n"):scanf&x):found=BinarySearch(a,x,n):if(found==~l){printf("未找到:printf("要査找的數(shù)在第個(gè)\tT,found^l):四?程序代碼變量定義說明：BinarySmarch()算法：a-＞數(shù)組key?＞要査找的元素left-〉左標(biāo)志right-）右標(biāo)志（n-＞數(shù)據(jù)個(gè)數(shù)）MainO主函數(shù):ound-》是否找到標(biāo)志，-1衣示未找到，找到其值為下標(biāo)要査找的元素曠＞元素個(gè)數(shù)i，j,P-〉循環(huán)控制變量（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數(shù)據(jù)個(gè)數(shù):”)：scanprintfC輸入數(shù)據(jù):\n"):for(i=0：i<n：i++){printW請(qǐng)輸入第崗個(gè)數(shù)據(jù)二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后的數(shù)據(jù)如下：”):for(i=0：i<n：i++){printfa[i]);}print￡("\“")：printfC輸入要査找的數(shù):"):scanx);intleft=O,right=n:found=BinarySearch(a,x,left,right):if(found==~l){printf(*未找到\n"):}else{primf("要ft找的數(shù)在第%d個(gè)\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數(shù)據(jù)個(gè)數(shù):”)：scan￡(飛d",&n):printfC輸入數(shù)據(jù)::for(i=0：i<n;i++){printfC請(qǐng)輸入第%d個(gè)數(shù)據(jù):",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("排序后的數(shù)據(jù)如下:w):for(i=0:i<n：i++){printf,a[i]):}printf<*\n*):printfL輸入要査找的數(shù):”〉：scanf&x)：intleft=0,right=n:found=BinarySearch(a,x,n):if(found==~l){printf("未找到\n*>:}else{printf("耍査找的數(shù)在第鴛d個(gè)\n*,found+l):}}五.結(jié)果運(yùn)行與分析找到要査找的數(shù)據(jù)：■LAU8?，'BDA0KUintnf?\?f-re*TwipVKftfi*jttf1illIfK:6也人請(qǐng)輸人第葉故據(jù):制hir：ji：:諭輛人笫.i—jftIRiHlllrI9XtHE卜■舅羽66埸柳人WPH4川?。褐谱Ρ?：‘：一未找到要查找的數(shù)據(jù):■-SlhrhgnjmrrrtWzrA：G對(duì)任妝p:iSVi人兀1個(gè)右戈帳：3ifi^；謝輸人斤?:力於JiCul.b“?U?j.iltJWIWi12zy?11A典?>IW[:IJy狛LE123143?69輸幾“卄期潮葉：七；?*F1?????』???六?心得與體會(huì)通過這次實(shí)驗(yàn)，鞏固了自己對(duì)二分搜索算法的理解，它是分治法的一個(gè)特殊例子，由此也對(duì)分治法有了更深一層次的認(rèn)識(shí)。分而治之，化復(fù)雜為簡(jiǎn)單，不只是在算法中，在口常生活中也是極其重要的。正如Bentl