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

1、。實(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)容及要求1 使用二分搜索算法查找任意N 個(gè)有序數(shù)列中的指定元素。2 通過上機(jī)實(shí)驗(yàn)進(jìn)行算法實(shí)現(xiàn)。3 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析，上交實(shí)驗(yàn)報(bào)告。4. 至少使用兩種方法進(jìn)行編程。三實(shí)驗(yàn)原理二分搜索算法也稱為折半查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用 O(log n) 完成搜索任務(wù)。【基本思想】將n 個(gè)元素分成個(gè)數(shù)大致相同的兩半，取an/2與欲查找的x 作比較，如果 x=

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

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

4、)scanf(%d,&ai);for (i=0;in-1;i+)。2。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);elseprintf(要查找的數(shù)在第%d 個(gè) n,found+1);方法三：迭代查找#include#define MAX 30int BinarySearch(int a,int &x,int n)int

5、left =0;int right=n-1;int middle;while(leftamiddle)left=middle+1;。3。else right=middle-1;return-1;main()int aMAX;int found,x,n,i,j,p;printf(數(shù)的個(gè)數(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=ai;ai=x;for(i=0;i 數(shù)組key- 要查找的元素left-左標(biāo)志r

6、ight-右標(biāo)志（n- 數(shù)據(jù)個(gè)數(shù)）Main() 主函數(shù)：ound- 是否找到標(biāo)志， -1 表示未找到，找到其值為下標(biāo) x- 要查找的元素n- 元素個(gè)數(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) return BinarySearch(a,key,mid+1,ri

7、ght); 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ù)個(gè)數(shù) :);scanf(%d,&n);printf(輸入數(shù)據(jù) :n);for(i=0;in;i+)。5。printf(請(qǐng)輸入第 %d個(gè)數(shù)據(jù) :,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;printf(排序后的數(shù)據(jù)如下：)

8、;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);elseprintf(要查找的數(shù)在第%d個(gè) n,found+1);（2）、非遞歸查找#include#define MAX 30int BinarySearch(int a, int key,int len)int mid=len/2;if (key=amid) return mid;。6。int

9、left=0;int right=len-1;while(left=right)/ 迭代查找mid=(right+left)/2;if(keyamid) left=mid+1;elsereturn mid;return -1;int main(void)int aMAX;int found,x,n,i,j,p;printf(數(shù)據(jù)個(gè)數(shù) :);scanf(%d,&n);printf(輸入數(shù)據(jù) :n);for(i=0;in;i+)printf(請(qǐng)輸入第 %d個(gè)數(shù)據(jù) :,i);scanf(%d,&ai);for (i=0;in-1;i+)/ 選擇排序p=i;for(j=i+1;jaj)p=j;if (

10、p!=j)x=ap;ap=ai;ai=x;printf(排序后的數(shù)據(jù)如下：);for(i=0;in;i+)printf(%d ,ai);。7。printf(n);printf(輸入要查找的數(shù):);scanf(%d,&x);int left=0,right=n;found=BinarySearch(a,x,n);if(found=-1)printf(未找到 n);elseprintf(要查找的數(shù)在第%d個(gè) n,found+1);五結(jié)果運(yùn)行與分析找到要查找的數(shù)據(jù)：未找到要查找的數(shù)據(jù)：。8。六心得與體會(huì)通過這次實(shí)驗(yàn)，鞏固了自己對(duì)二分搜索算法的理解，它是分治法的一個(gè)特殊例子，由此也對(duì)分治法有了更深一層次的認(rèn)識(shí)。分而治之，化復(fù)雜為簡單，不只是在算法中，在日常生活中也是極其重要的。正如Bentley 在他的著作 Writing Correct Programs 中所說，能夠完整的寫出二分搜索算法是很難的，準(zhǔn)確來說，在固定的時(shí)間內(nèi)很大一部分人是不能完成這個(gè)任務(wù)的，因?yàn)槠渲?/p>