当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

二分查找排序算法

发表于: 2014-07-21   作者:周凡杨   来源:转载   浏览:
摘要: 一:概念 二分查找又称 折半查找( 折半搜索/ 二分搜索),优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而 查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表 分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步

一:概念

二分查找又称折半查找折半搜索/二分搜索),优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而 查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表 分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录, 使查找成功,或直到子表不存在为止,此时查找不成功。

 

二:原理

二分查找的基本思想是:(设R[low..high]是当前的查找区间)
 1)首先确定该区间的中点位置:

    
           mid=(low+high)/2
 2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下:
     ①若R[mid].key>K,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]

     ②类似地,若R[mid].key<K,则要查找的K必在mid的右子表R[mid+1..n]中,即新的查找区间是右子表R[mid+1..n]。下一次查找是针对新的查找区间进行的。

     因此,从初始的查找区间R[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。

 

三:用JAVA实现

 
publicstaticint binarySearch2(int[] srcArray,int des) throws Exception{
int beginIndex = 0;
int endIndex = srcArray.length-1;
int middleIndex = beginIndex+((endIndex-beginIndex)>>1);
while(srcArray[middleIndex] != des && endIndex > beginIndex && (endIndex-1)>beginIndex){
    if(srcArray[middleIndex] < des){
        beginIndex = middleIndex;
    }elseif(srcArray[middleIndex] > des){
        endIndex = middleIndex;
    }
         middleIndex = beginIndex+((endIndex-beginIndex)>>1);
     }
     if(srcArray[middleIndex] == des){
         return middleIndex;   //表示找到了,返回该值的下标
     }else{
         thrownew Exception("没有找到");       //表示没有找到
     }
}
   上面这是自己根据对二分查找算法原理的理解写出来的代码。

 

下面的是摘自己网上的写法:

 
public static int binarySearch3(int[] srcArray,int des) throws Exception{
		int beginIndex = 0;
		int endIndex = srcArray.length-1;
		while(beginIndex <= endIndex){
			int middleIndex = beginIndex+((endIndex-beginIndex)>>1);
			if(srcArray[middleIndex] < des){
				beginIndex = middleIndex+1;
			}else if(srcArray[middleIndex] > des){
				endIndex = middleIndex-1;
			}else{
				return middleIndex;
			}
		}
		throw new Exception("没有找到");//表示没有找到
	}
 

 

四:复杂度分析

时间复杂度     折半搜索每次把搜索区域减少一半,时间复杂度为O(logn) n代表集合中元素的个数)
空间复杂度

      O(1)虽以递归形式定义,但是尾递归,可改写为循环。

 

二分查找的优点和缺点:

  虽然二分查找的效率高,但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。
  二分查找只适用顺序存储结构。为保持表的有序性,在顺序结构里插入和删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
  对那些查找少而又经常需要改动的线性表,可采用链表作存储结构,进行顺序查找。链表上无法实现二分查找。

 

 

五:高级思想

对于二分查找算法,Jon Bentley曾在《编程珠玑》一书中说:90%程序员无法正确实现二分查找算法的。看来该算法中有些猫腻,是不是我们没有注意到什么点?

 

   //二分查找V0.1实现版  
   //首先要把握下面几个要点:  
   //right=n-1 => while(left <= right) => right=middle-1;  
   //right=n   => while(left <  right) => right=middle;  
   //middle的计算不能写在while循环外,否则无法得到更新。  
  int binary_search(int array[],int n,int value)  
  {  
       int left=0;  
       int right=n-1;  
       //如果这里是int right = n 的话,那么下面有两处地方需要修改,以保证一一对应:  
       //1、下面循环的条件则是while(left < right)  
       //2、循环内当array[middle]>value 的时候,right = mid  
       
         while (left<=right)          //循环条件,适时而变  
         {  
           int middle=left + ((right-left)>>1);  //防止溢出,移位也更高效。同时,每次循环都需要更新。  
           if (array[middle]>value){  
               right =middle-1;   //right赋值,适时而变  
            }else if(array[middle]<value)  {  
               left=middle+1;  
            }else  
               return middle;    
           //可能会有读者认为刚开始时就要判断相等,但毕竟数组中不相等的情况更多  
           //如果每次循环都判断一下是否相等,将耗费时间  
        }  
        return -1;  
    }  
 

 

从上面的代码及注释中,可以总结到   
  陷阱1 middle = (left+right)>>1; 这样的话leftright的值比较大的时候,其和可能溢出。
  陷阱2 预防while循环时出现死循环。例如:              
 right = n;
while(left <  right) {
     …
    right = middle;
     …
}
   如果搜索数组中不存在的数字的时候,可能会导致死循环,因为最后left = middle, right = middle + 1,这样每次更新leftmiddle总是不变的。    

 

参考资料

http://baike.baidu.com/view/610605.htm?fr=aladdin

http://blog.csdn.net/v_july_v/article/details/7093204

http://www.zhuoda.org/weiking/67932.html

http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.2.2.1.htm

http://blog.csdn.net/v_july_v/article/details/7093204

http://www.zhuoda.org/weiking/67932.html

 

 

 

 

 

二分查找排序算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
编程之美在于算法之美,先来看看二分查找的算法: 隐藏条件:二分查找必须是有序的,从小到大,或从
二分查找 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为
二分查找算法前提有2个:1.必须采用顺序存储结构,2.必须按关键字有序排列。时间复杂度为O(logn)。
算法-查找之二二分查找 顺序查找【算法-查找之一】顺序查找是最简单的查找策略,易于分析,适用于小
08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的
二分算法的定义不在多说了,百度一下就知道(支持国产) import sys source = [1,2,3,4,5,6,7,8,9,1
学过数据结构,当然当年也学过算法的时间复杂度的,不知道当年是不是会推倒时间复杂度,大概也就是
二分查找法要求被查找的线性表已经排序。 每一次查找,按中间索引把表分为左右两部分,通过对比中间
二分查找 题目:查找学生信息 时间限制:1秒 内存限制:32M 特殊判题:否 题目描述: 输入N个学术的
08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号