二分搜索算法实验报告

实验一二分搜索算法实验报告一．实验目的1、理解分治算法的概念和基本要素；2、理解递归的概念；3、掌握设计有效算法的分治策略；4、通过二分搜索技术学习分治策略设计技巧；二．实验内容及要求1．使用二分搜索算法查找任意N个有序数列中的指定元素。2．通过上机实验进行算法实现。3．保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。4.至少使用两种方法进行编程。三．实验原理二分搜索算法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。【基本思想】将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。第一个二分搜索算法早在1946年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《WritingCorrectPrograms》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。方法一：直接查找穷举法遍历方法二：递归查找#includestdio.h#defineMAX30intBinarySearch(inta[],int&x,intleft,intright){if(leftright){return-1;}else{left=(left+right)/2;if(x==a[left])returnleft;else{if(xa[left])BinarySearch(a,x,left+1,right);elseBinarySearch(a,x,left*2-right,left+1);}}}main(){inta[MAX];intfound,x,n,i,j,p;printf(输的个数\n);scanf(%d,&n);printf(数组数据\n);for(i=0;in;i++){scanf(%d,&a[i]);}for(i=0;in-1;i++){p=i;for(j=i+1;jn;j++)if(a[p]a[j])p=j;if(p!=j){x=a[p];a[p]=a[i];a[i]=x;}}for(i=0;in;i++){printf(%d,a[i]);}printf(输入要查找的数\n);scanf(%d,&x);found=BinarySearch(a,x,0,n);if(found==-1){printf(未找到\n);}else{printf(要查找的数在第%d个\n,found+1);}}方法三：迭代查找#includestdio.h#defineMAX30intBinarySearch(inta[],int&x,intn){intleft=0;intright=n-1;intmiddle;while(left=right){middle=(left+right)/2;if(x==a[middle])returnmiddle;if(xa[middle])left=middle+1;elseright=middle-1;}return-1;}main(){inta[MAX];intfound,x,n,i,j,p;printf(数的个数\n);scanf(%d,&n);printf(数组数据\n);for(i=0;in;i++){scanf(%d,&a[i]);}for(i=0;in-1;i++){p=i;for(j=i+1;jn;j++)if(a[p]a[j])p=j;if(p!=j){x=a[p];a[p]=a[i];a[i]=x;}}for(i=0;in;i++){printf(%d,a[i]);}printf(输入要查找的数\n);scanf(%d,&x);found=BinarySearch(a,x,n);if(found==-1){printf(未找到\n);}else{printf(要查找的数在第%d个\n,found+1);}}四．程序代码变量定义说明：BinarySearch()算法：a-数组key-要查找的元素left-左标志right-右标志（n-数据个数）Main()主函数：ound-是否找到标志，-1表示未找到，找到其值为下标x-要查找的元素n-元素个数i，j，p-循环控制变量（1）、递归查找#includestdio.h#defineMAX30intBinarySearch(inta[],intkey,intleft,intright){intmid=(right-right)/2+left;if(a[mid]==key){returnmid;}if(left=right){return-1;}elseif(keya[mid]){returnBinarySearch(a,key,mid+1,right);}elseif(keya[mid]){returnBinarySearch(a,key,left,mid-1);}return-1;}intmain(void){inta[MAX];intfound,x,n,i,j,p;printf(数据个数:);scanf(%d,&n);printf(输入数据:\n);for(i=0;in;i++){printf(请输入第%d个数据:,i);scanf(%d,&a[i]);}for(i=0;in-1;i++)//选择排序{p=i;for(j=i+1;jn;j++)if(a[p]a[j])p=j;if(p!=j){x=a[p];a[p]=a[i];a[i]=x;}}printf(排序后的数据如下：);for(i=0;in;i++){printf(%d,a[i]);}printf(\n);printf(输入要查找的数:);scanf(%d,&x);intleft=0,right=n;found=BinarySearch(a,x,left,right);if(found==-1){printf(未找到\n);}else{printf(要查找的数在第%d个\n,found+1);}}（2）、非递归查找#includestdio.h#defineMAX30intBinarySearch(inta[],intkey,intlen){intmid=len/2;if(key==a[mid]){returnmid;}intleft=0;intright=len-1;while(left=right){//迭代查找mid=(right+left)/2;if(keya[mid]){right=mid-1;}elseif(keya[mid]){left=mid+1;}else{returnmid;}}return-1;}intmain(void){inta[MAX];intfound,x,n,i,j,p;printf(数据个数:);scanf(%d,&n);printf(输入数据:\n);for(i=0;in;i++){printf(请输入第%d个数据:,i);scanf(%d,&a[i]);}for(i=0;in-1;i++)//选择排序{p=i;for(j=i+1;jn;j++)if(a[p]a[j])p=j;if(p!=j){x=a[p];a[p]=a[i];a[i]=x;}}printf(排序后的数据如下：);for(i=0;in;i++){printf(%d,a[i]);}printf(\n);printf(输入要查找的数:);scanf(%d,&x);intleft=0,right=n;found=BinarySearch(a,x,n);if(found==-1){printf(未找到\n);}else{printf(要查找的数在第%d个\n,found+1);}}五．结果运行与分析找到要查找的数据：未找到要查找的数据：六．心得与体会通过这次实验，巩固了自己对二分搜索算法的理解，它是分治法的一个特殊例子，由此也对分治法有了更深一层次的认识。分而治之，化复杂为简单，不只是在算法中，在日常生活中也是极其重要的。正如Bentley在他的著作《WritingCorrectPrograms》中所说，能够完整的写出二分搜索算法是很难的，准确来说，在固定的时间内很大一部分人是不能完成这个任务的，因为其中的边界判定问题需要引起很大的注意，一不留神就容易犯错，导致结果的错误，而这种边界问题有很难找到，只有通过一步一步的演算才能完全正确的推导出来。这告诫我们，熟能生巧，只有在生活中多练习，当真正需要的时候，才能够信手拈来。