二分搜索算法实验报告

1、实验一二分搜索算法实验报告一 实验目的1、 理解分治算法的概念和基本要素；2、 理解递归的概念；3、 掌握设计有效算法的分治策略；4、 通 过二分搜索技术学习分治策略设计技巧；二实验内容及要求1 使用二分搜索算法查找任意N 个有序数列中的指定元素。2 通过上机实验进行算法实现。3 保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。4 至少使用两种方法进行编程。三实验原理二分搜索算法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n) 完成搜索任务。【基本思想】将n 个元素分成个数大致相同的两半，取an/2 与欲查找的x 作比较，如果x=a

2、n/2则找到x,算法终止。如果 xan/2 ，则我们只要在数组a 的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了，但是第一个完全正确的二分搜索算法直到1962 年才出现。Bentley 在他的著作Writing Correct Programs 中写道，90%的计算机专家不能在2 小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。方法一：直接查找穷举法遍历方法二：递归查找#include#define MAX 30i

3、nt 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( 输的个数n);scanf(%d,&n);printf( 数组数据n);for(i=0;in;i+)sca

4、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;for(i=0;in;i+) printf(%d ,ai);printf( 输入要查找的数n);scanf(%d,&x);found=BinarySearch(a,x,0,n);if(found=-1) printf( 未找到 n);elseprintf( 要查找的数在第%d 个 n,found+1);方法三：迭代查找#include#define MAX 30int BinarySearch(int a,int &x,int n)int le

5、ft =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( 数的个数n);scanf(%d,&n);printf( 数组数据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 数组key-要查找的元素left- 左标志right-

6、 右标志(n-数据个数)Main()主函数：ound-是否找到标志，-1表示未找到，找到其值为下标x-要查找的元素 n-元素个数i, j, p-循环控制变量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,right); else if(

7、keyamid) return BinarySearch(a,key,left,mid- 1);return -1;int main(void)int aMAX;int found,x,n,i,j,p;printf( 数据个数:);scanf(%d,&n);printf( 输入数据:n);for(i=0;in;i+)printf( 请输入第%d 个数据 :,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( 排序后的数据如下：);for(i=0;in;i+)p

8、rintf(%d ,ai);printf(n);printf( 输入要查找的数:);scanf(%d,&x);int left=0,right=n;found=BinarySearch(a,x,left,right);if(found=-1)printf( 未找到 n);elseprintf( 要查找的数在第%d 个 n,found+1);2)、非递归查找#include#define MAX 30int BinarySearch(int a, int key,int len)int mid=len/2;if (key=amid) return mid;int left=0;int right

9、=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( 数据个数:);scanf(%d,&n);printf( 输入数据:n);for(i=0;in;i+)printf( 请输入第%d 个数据 :,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

10、i;ai=x;printf( 排序后的数据如下：);for(i=0;in;i+)printf(%d ,ai);printf(n);printf(输入要查找的数：)；scanf(%d,&x);int left=0,right=n;found=BinarySearch(a,x,n);if(found=-1) printf(未找到 n);else printf(要查找的数在第 %d个n,found+1);五.结果运行与分析找到要查找的数据：未找到要查找的数据:六.心得与体会通过这次实验，巩固了自己对二分搜索算法的理解，它是分治法的一个特 殊例子，由此也对分治法有了更深一层次的认识。分而治之，化复杂为简单， 不只是在算法中，在日常生活中也是极其重要的。正如 Bentley在他的著作Writing Correct Programs中所说，能够完整