欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找排序算法

程序员文章站 2024-03-20 10:07:40
...

一:概念

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

 

二:原理

二分查找的基本思想是:(设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;  
    }  
 

 

从上面的代码及注释中,可以总结到  
  陷阱1middle = (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