二分搜索算法实验报告.doc

。实验一 二分搜索算法实验报告一 实验目的1、 理解分治算法的概念和基本要素；2、 理解递归的概念；3、 掌握设计有效算法的分治策略；4、 通过二分搜索技术学习分治策略设计技巧；二实验内容及要求1 使用二分搜索算法查找任意N个有序数列中的指定元素。2 通过上机实验进行算法实现。3 保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。4. 至少使用两种方法进行编程。三实验原理二分搜索算法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。【基本思想】将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如果xan/2，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作Writing Correct Programs中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。 方法一：直接查找 穷举法遍历 方法二：递归查找#include#define MAX 30int 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(输的个数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;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,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=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 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(数据个数:); 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+) 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) 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(数据个数:); 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+) 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); 5 结果运行与分析找到要查找的数据：未找到要查找的数据：六心得与体会通过这次实验，巩固了自己对二分搜索算法的理解，它是分治法的一个特殊例子，由此也对分治法有了更深一层次的认识。分而治之，化复杂为简单，不只是在算法中，在日常生活中也是极其重要的。正如Bentley在他的著作Writing Correct Programs中所说，能够完整的写出二分搜索算法是很难的，准确来说，在固定的时间内很大一部分人是不能完成这个任务的，