广汉移动网站建设,沂南网站设计,网站的服务器和空间,自学seo大概需要多久二分搜索算法是运用分治策略的典型例子。给定己排好府的 n个元素a10:n-1]#xff0c;现要在这n个元素中找出一特定元素3。首先较容易想到的是用顺序搜索方法#xff0c;逐个比较a10:1-1]中元素#xff0c;直至找出元素#xff0c;或搜索遍整个数组后确定#xff0c;不在其…二分搜索算法是运用分治策略的典型例子。给定己排好府的 n个元素a10:n-1]现要在这n个元素中找出一特定元素3。首先较容易想到的是用顺序搜索方法逐个比较a10:1-1]中元素直至找出元素或搜索遍整个数组后确定不在其中。这个方法没有很好地利用n个元素已排好序这个条件因此在最坏情况下顺序搜索方法需要 O1次比较。二分搜索方法充分利用了元素间的次序关系采用分治策略可在最坏情況下用 O(ogn)时间完成搜索任务。二分搜索算法的基本思想是将n个元素分成个数大致相同的两半取aln/21与x 作比较。如果x-aln/2]则我到x算法终止如果xain/2]则只在数组。 的左半部继续搜索 3如果saln/2]则只在数组a 的右半部继续搜索x。具体算法可描述如下templateclass Type
int BinarySearch(Type a[],const Type x,int n)
{//在a[0]a[1]...a[n-1]中搜索x//找到x时返回其在数组中的位置否则返回-1int left0; int rightn-1;while(leftright){int middle(leftright)/2;if(xa[middle]){return middle;}if(xa[middle]){leftmiddle1;}elserightmiddle-1;}return-1;//未找到x
}容易看出每执行一次算法的 while 福环待搜索数组的大小减小一半。因此在取多情况下whie 循环被执行了 0o 2)次。循环体肉运算需要 Q()时间因此整个算法在最动情况下的计算时间复杂性为 Ologn)。三分搜索算法的思想易手理解但是要写一个正确的二分搜索算法也不是一件简单的事。Knuth在他的著作 “The Art of Coroputer Prograraming : Sorting and Searching”中提到第一个二分搜素算法早在 1946年就出现丁但是第一个完全正确的二分搜索算法直到1946年才出现。总结后期还会更新课程太紧后面会改进这篇文章还有所有需要改进的文章
