二分搜索算法實驗報告參考模板

1、實驗一 二分搜索算法實驗報告一 實驗?zāi)康?、 理解分治算法的概念和基本要素；2、 理解遞歸的概念；3、 掌握設(shè)計有效算法的分治策略；4、 通過二分搜索技術(shù)學習分治策略設(shè)計技巧；二實驗內(nèi)容及要求1 使用二分搜索算法查找任意N個有序數(shù)列中的指定元素。2 通過上機實驗進行算法實現(xiàn)。3 保存和打印出程序的運行結(jié)果，并結(jié)合程序進行分析，上交實驗報告。4. 至少使用兩種方法進行編程。三實驗原理二分搜索算法也稱為折半查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務(wù)。【基本思想】將n個元素分成個數(shù)大致相同的兩半，取an/2與欲查找的x作比較，如果x=an/2則

2、找到x，算法終止。如果xan/2，則我們只要在數(shù)組a的右半部繼續(xù)搜索x。二分搜索法的應(yīng)用極其廣泛，而且它的思想易于理解。第一個二分搜索算法早在1946 年就出現(xiàn)了，但是第一個完全正確的二分搜索算法直到1962年才出現(xiàn)。Bentley在他的著作Writing Correct Programs中寫道，90%的計算機專家不能在2小時內(nèi)寫出完全正確的二分搜索算法。問題的關(guān)鍵在于準確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數(shù)的各種情況，其實整理后可以發(fā)現(xiàn)它的具體算法是很直觀的。2 / 11 方法一：直接查找 窮舉法遍歷 方法二：遞歸查找#include#define MAX 30int

3、 BinarySearch(int a,int &x,int left,int right) if(leftright) return -1; else left=(left+right)/2; if(x=aleft) return left; else if(xaleft) BinarySearch(a,x,left+1,right); else BinarySearch(a,x,left*2-right,left+1); main()int aMAX; int found,x,n,i,j,p; printf(輸?shù)膫€數(shù)n); scanf(%d,&n); printf(數(shù)組數(shù)據(jù)n); for(

4、i=0;in;i+) scanf(%d,&ai); for (i=0;in-1;i+) p=i; for (j=i+1;jaj) p=j; if (p!=j) x=ap; ap=ai; ai=x; for(i=0;in;i+) printf(%d ,ai); printf(輸入要查找的數(shù)n); scanf(%d,&x); found=BinarySearch(a,x,0,n); if(found=-1) printf(未找到n); else printf(要查找的數(shù)在第 %d個n,found+1); 方法三：迭代查找#include#define MAX 30int BinarySearch(

5、int a,int &x,int n) int left =0; int right=n-1; int middle; while(leftamiddle) left=middle+1; else right=middle-1; return-1;main() int aMAX; int found,x,n,i,j,p; printf(數(shù)的個數(shù)n); scanf(%d,&n); printf(數(shù)組數(shù)據(jù)n); for(i=0;in;i+) scanf(%d,&ai); for (i=0;in-1;i+) p=i; for (j=i+1;jaj) p=j; if (p!=j) x=ap; ap=a

6、i; ai=x; for(i=0;i數(shù)組key-要查找的元素left-左標志right-右標志（n-數(shù)據(jù)個數(shù)）Main()主函數(shù)：ound-是否找到標志，-1表示未找到，找到其值為下標x-要查找的元素n-元素個數(shù)i，j，p-循環(huán)控制變量（1） 、遞歸查找#include#define MAX 30int BinarySearch(int a,int key,int left,int right) int mid=(right-right)/2+left; if(amid=key) return mid; if(left=right) return -1; else if(keyamid) re

7、turn BinarySearch(a,key,mid+1,right); else if(keyamid) return BinarySearch(a,key,left,mid- 1); return -1; int main(void)int aMAX; int found,x,n,i,j,p; printf(數(shù)據(jù)個數(shù):); scanf(%d,&n); printf(輸入數(shù)據(jù):n); for(i=0;in;i+) printf(請輸入第%d個數(shù)據(jù):,i); scanf(%d,&ai); for (i=0;in-1;i+)/選擇排序 p=i;for(j=i+1;jaj)p=j;if (p!=

8、j) x=ap; ap=ai;ai=x; printf(排序后的數(shù)據(jù)如下：); for(i=0;in;i+) printf(%d ,ai); printf(n); printf(輸入要查找的數(shù):); scanf(%d,&x); int left=0,right=n; found=BinarySearch(a,x,left,right); if(found=-1) printf(未找到n); else printf(要查找的數(shù)在第%d個n,found+1); （2） 、非遞歸查找#include#define MAX 30int BinarySearch(int a, int key,int l

9、en) int mid=len/2; if (key=amid) return mid; int left=0; int right=len-1; while(left=right) /迭代查找 mid=(right+left)/2; if(keyamid) left=mid+1; else return mid; return -1; int main(void)int aMAX; int found,x,n,i,j,p; printf(數(shù)據(jù)個數(shù):); scanf(%d,&n); printf(輸入數(shù)據(jù):n); for(i=0;in;i+) printf(請輸入第%d個數(shù)據(jù):,i); sca

10、nf(%d,&ai); for (i=0;in-1;i+)/選擇排序 p=i;for(j=i+1;jaj)p=j;if (p!=j) x=ap; ap=ai;ai=x; printf(排序后的數(shù)據(jù)如下：); for(i=0;in;i+) printf(%d ,ai); printf(n); printf(輸入要查找的數(shù):); scanf(%d,&x); int left=0,right=n; found=BinarySearch(a,x,n); if(found=-1) printf(未找到n); else printf(要查找的數(shù)在第%d個n,found+1); 5 結(jié)果運行與分析找到要查找的數(shù)據(jù)：未找到要查找的數(shù)據(jù)：六心得與體會通過這次實驗，鞏固了自己對二分搜索算法的理解，它是分治法的一個特殊例子，由此也對分治法有了更深一層次的認識。分而治之，化復雜為簡單，不只是在算法中，在日常生活中也是極其重要的。正如Bentley在他的著作Writing Correct Program