二分探索法查找数据课程设计.doc

用二分搜索法查找数据数学与计算机学院课程设计说明书课 程 名 称: 算法设计与分析-课程设计 课 程 代 码: 8701479 题 目: 用二分搜索法查找数据 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 年 月 日完 成 时 间: 年 月 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日目 录摘 要1 引言21.1 问题的提出21.2二分搜索法目前现状31.3二分法41.4 任务与分析5 二分搜索法详细设计62.1二分搜索算法62.2二分法算法的实现即编程72.3二分法应用举例13 程序测试机运行结果143.1 程序测试过程143.2 运行结果163.3 算法复杂度分析174. 总结19摘 要折半查找法也称为二分查找法或二分搜索法，它充分利用了元素间的次序关系，采用分治策略而较快地查找数据。现要求给出一个待查找的实例，并给出二分搜索算法，编写程序利用此算法实现查找。它的基本思想是，将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如果xan/2，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解，但是要写一个正确的二分搜索算法也不是一件简单的事。第一个二分搜索算法早在1946年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作Writing Correct Programs中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况。关键词：二分法 折半 查找 引言1.1 问题的提出二分搜索法的应用极其广泛，而且它的思想易于理解，但是要写一个正确的二分搜索算法也不是一件简单的事。第一个二分搜索算法早在1946年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作Writing Correct Programs中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的，我们可用C+描述如下： template int BinarySearch(Type a,const Type& x,int n) int left=0;int right=n-1; while(leftamiddle) left=middle+1; else right=middle-1; return -1; 模板函数BinarySearch在a0=a1=.=an-1共n个升序排列的元素中搜索x,找到x时返回其在数组中的位置，否则返回-1。容易看出，每执行一次while循环，待搜索数组的大小减少一半,因此整个算法在最坏情况下的时间复杂度为O(log n)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。 二分搜索法的局限性：必须是在有序的元素中进行，不能在无序的元素中使用。1.2二分搜索法目前现状二分法现在已经运用到各个领域，在数学方面，一般地，对于函数f(x),如果存在实数c,当x=c时，若f(c)=0,那么把x=c叫做函数f(x)的零点。解方程即要求f(x)的所有零点。通过每次把f(x)的零点所在小区间收缩一半的方法，使区间的两个端点逐步迫近函数的零点，以求得零点的近似值，这种方法叫做二分法。在经济学方面，传统的经济学家把经济分为实物经济和货币经济两部分，其中，经济理论分析实际变量的决定，而货币理论分析价格的决定，两者之间并没有多大的关系，这就是所谓的二分法。在哲学方面，又称二分说，爱利亚学派芝诺四大著名悖论之一证明运动是不可能的。其主要思路是：假设一个存在物经过空间而运动，为了穿越某个空间，就必须穿越这个空间的一半。为了穿越这一半，就必须穿越这一半的一半；以此类推，直至无穷。所以，运动是不可能的。在日常生活中，即将所有的事物根据其属性分成两种。错误的分类可能导致逻辑谬论，如：非黑即白，不是忠的就是奸的。这很明显忽略了中间状态的存在。正确的分类法应如：白-非白。但是二分法在计算机领域是用得最多的，他可以坚决许多复杂的问题，使得复杂的问题变得简单易解。1.3二分法在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。比较自然的想法是一个一个地扫描L的所有元素，直到找到x为止。这种方法对于有n个元素的线性表在最坏情况下需要n次比较。一般来说，如果没有其他的附加信息，在有n个元素的线性表中查找一个元素在最坏情况下都需要n次比较。下面我们考虑一种简单的情况。假设该线性表已经排好序了，不妨设它按照主键的递增顺序排列（即由小到大排列）。在这种情况下，我们是否有改进查找效率的可能呢？如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：比较x和L中任意一个元素Li，若x=Li，则x在L中的位置就是i；如果xLi，同理我们只要在Li的后面查找x即可。无论是在Li的前面还是后面查找x，其方法都和在L中查找x一样，只不过是线性表的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。很显然此问题分解出的子问题相互独立，即在Li的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。于是我们得到利用分治法在有序表中查找元素的算法1.4 任务与分析1设计内容：折半查找法也称为二分查找法或二分搜索法，它充分利用了元素间的次序关系，采用分治策略而较快地查找数据。现要求给出一个待查找的实例，并给出二分搜索算法，编写程序利用此算法实现查找。2设计要求：（1）给出分治思想；（2）给出一个实际应用；（3）给出二分搜索算法；（4）编程实现算法；（5）给出算法的时间复杂度分析。 二分搜索法详细设计2.1二分搜索算法下面我们考虑一种简单的情况。假设该线性表已经排好序了，不妨设它按照主键的递增顺序排列（即由小到大排列）。在这种情况下，我们是否有改进查找效率的可能呢？如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：比较x和L中任意一个元素Li，若x=Li，则x在L中的位置就是i；如果xLi，同理我们只要在Li的后面查找x即可。无论是在 Li的前面还是后面查找x，其方法都和在L中查找x一样，只不过是线性表的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。很显然 此问题分解出的子问题相互独立，即在Li的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。于是我们得到利用分治法在有序表中查找元素的算法。function Binary_Search(L,a,b,x);beginif ab then return(-1)else beginm:=(a+b) div 2;if x=Lm then return(m)else if xLm thenreturn(Binary_Search(L,m+1,b,x);else return(Binary_Search(L,a,m-1,x);end; end;2.2二分法算法的实现即编程在常规的二分查找法查找到一个符合条件数便会停止，如果数组中存在多个符合条件的数，并不会全部输出 ，二分查找法（折半查找法）的算法如下：#include #include #define ARR_MAX 100 /定义数组的最大长度/为方便测试，此函数自动用随机数填充数组void fillArray(int * Array,int Length,int Range); /二分查找法要求查找目标是有序数组，此函数来对数组排序void sortArray(int * Array,int Length); /用二分法查找，改进后的搜索函数可查找出全部符合条件的数/并输出找到数的数量和这些数在数中的位置void searchNumber(int * Array,int Length,int Num); void main()int nArrayARR_MAX;int nLength=ARR_MAX; /指定在数组前 nLength 项进行操作int nFillRange=50; /规定用来填充数组的随机数的取值范围int nNum=0,nFind=0;char cContinue;fillArray(nArray,nLength,nFillRange); /填充数组sortArray(nArray,nLength); /数组排序loopSearchAgain: coutendlnNum; /取得待对比的整数searchNumber(nArray,nLength,nNum); /查找/询问是否继续在数组中查找新的数值coutendlcContinue;if(cContinue=C)|(cContinue=c)goto loopSearchAgain;/填充void fillArray(int * Array,int Length,int Range)for(int i=0;iLength;i+)Array=rand() % Range;/coutArrayi=Arrayendl; /测试代码，用来输出填充过程/排序void sortArray(int * Array,int Length)int i,j,t;for(i=0;iLength-1;i+)for(j=i;jArrayj)t=Array;Array=Arrayj;Arrayj=t;/for(i=0;iLength;i+)coutArrayi=Arrayendl;/测试代码，用来输出排序结果/查找void searchNumber(int * Array,int Length,int Num)int nStart=0,nEnd=Length-1,nMiddle,nFound=0;while(nStart=nEnd)nMiddle=(nStart+nEnd)/2;/coutStart=nStart End=nEnd Middle=nMiddle1)cout找到 nFound 个符合条件的数，从 ArraynMin 到 ArraynMax 。endl;break;elsecout在 ArraynMiddle找到一个符合条件的数。Num) /判断方向，折半继续查找nEnd=nMiddle-1; elsenStart=nMiddle+1;if(nFound=0)cout数组中没找到符合条件的数。endl;2.3二分法应用举例用二分法求方程的近似解问题：一元二次方程可用判别式判定根的存在性，可用求根公式求方程的根.但对于一般的方程，虽然可用零点存在性定理判定根的存在性，而没有公式. 求根：如何求得方程的根呢？例 用二分法求函数f (x) = x3 3的一个正实数零点(精确到0.1).由于f (1) = 20，f (2) = 50，因此可以确定区间1，2作为计算的初始区间，用二分法逐步计算，列表如下：端点或中点的横坐标计算端点或中点的函数值定区间a0 = 1，b0 = 2f(1)= 2，f(2)=51，2f (x0) = 0.37501，1.5 f (x1) = 1.046901.25，1.5f (x2) = 0.400401.375，1.5f (x3) = 0.029501.4375，1.5f (x4) = 0.168401.4375，1.46875f (x5)01.4375，1.453125x6 = 1.4453125f (x6)01.4375，1.4453125由上表的计算可知区间1.4375，1.4453125的左、右端点精确到0.1所取的近似值都是1.4，所以1.4可作为所求函数的一个正实数零点的近似值. 程序测试机运行结果3.1 程序测试过程1.我们的运行幻境：操作系统：windows XP ，语言环境：VC+ 6.0。2. 核心代码及调试过程int main() int L100,search,pos,len; coutlen;cout请输入长度为len的一个升序数组：;for(int i=0;iLi; coutsearch;pos=binarySearh(L,len,search);if(pos = -1) cout非递归算法没有找到该数endl; else cout非递归算法找到该数的位置为：pos+1endl; pos = binarySearh2(L,0,(len-1),search);if(pos = -1) cout递归算法没有找到该数endl; else cout递归算法找到该数的位置为：pos+1endl; system(pause);return 0; int binarySearh(int Arr,int len,int search) /二分查找非递归算法函数，返回找到的位置int low,mid,high; low=0;high=len-1;while(lowsearch) high=mid-1;/如果mid指针指向的元素值大于查找元素，令high指针指向mid指针前一个元素else low=mid+1;/如果mid指针指向的元素值小于查找元素，令low 指针指向mid的后一个元素return -1;/没有找到则返回-1 int binarySearh2(int Arr,int low,int high,int search)/二分查找递归算法函数，返回找到的位置 if(lowsearch) high=mid-1;/如果mid指针指向的元素值大于查找元素，令high指针指向mid指针前一个元素 else low=mid+1;/如果mid指针指向的元素值小于查找元素，令low 指针指向mid的后一个元素 return binarySearh2(Arr,low,high,search);/如果没找到，递归寻找 return -1;/没有找到则返回-13.2 运行结果我们输入长度为13的数组：当K=70时，运行结果为：当K=45时，我们会发现，数据中没有该数，起运行结果