《二分搜索算法实验报告9页》由会员分享，可在线阅读，更多相关《二分搜索算法实验报告9页（9页珍藏版）》请在金锄头文库上搜索。
1、实验一 二分搜索算法实验报告一 实验目的1、 理解分治算法的概念和基本要素；2、 理解递归的概念；3、 掌握设计有效算法的分治策略；4、 通过二分搜索技术学习分治策略设计技巧；二实验内容及要求1 使用二分搜索算法查找任意N个有序数列中的指定元素。2 通过上机实验进行算法实现。3 保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。4. 至少使用两种方法进行编程。三实验原理二分搜索算法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。【基本思想】将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则
2、找到x，算法终止。如果xan/2，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作Writing Correct Programs中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。 方法一：直接查找 穷举法遍历 方法二：递归查找#include#define MAX 30int Binar
3、ySearch(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(输的个数n); scanf(%d,&n); printf(数组数据n); for(i=0;in
4、;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(输入要查找的数n); scanf(%d,&x); found=BinarySearch(a,x,0,n); if(found=-1) printf(未找到n); else printf(要查找的数在第 %d个n,found+1); 方法三：迭代查找#include#define MAX 30int BinarySearch(int a,
5、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(数的个数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=
6、x; for(i=0;i数组key-要查找的元素left-左标志right-右标志（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 B
7、inarySearch(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(数据个数:); 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=a
8、p; ap=ai;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,left,right); if(found=-1) printf(未找到n); else printf(要查找的数在第%d个n,found+1); （2） 、非递归查找#include#define MAX 30int BinarySearch(int a, int key,int len) in
9、t 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(数据个数:); 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;jn;j
