`
周凡杨
  • 浏览: 234299 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

二分查找排序算法

阅读更多

一:概念

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

 

二:原理

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

 

 

 

 

 

0
0
分享到:
评论

相关推荐

    二分查找排序算法.zip

    二分查找排序算法是一种高效的排序方法,它是基于二分查找思想和插入排序的结合体。在计算机科学中,排序算法是处理数据集合的一种基础方法,它使得数据按照特定的顺序排列,例如升序或降序。二分查找排序算法特别...

    基于二分排序法时间复杂度的求解过程.pdf

    论文首先介绍了算法分析的目的和重要性,然后对二分查找排序法的时间复杂度进行了详细的分析。 在算法分析中,时间复杂度是指程序运行从开始到结束所需要的时间。它通常用大O符号表示,例如O(n)表示算法的执行时间...

    二分查找算法和冒泡排序算法

    二分查找算法与冒泡排序算法是计算机科学中两种基础且重要的算法,它们在数据处理和数组操作中扮演着至关重要的角色。 首先,我们来详细探讨递归二分查找算法。二分查找,也称为折半查找,是一种在有序数组中查找...

    数据结构查找、排序、二分查找、折半查找算法

    在这个主题中,我们主要关注查找和排序算法,特别是二分查找(折半查找)算法。这些算法在实际编程中具有广泛应用,包括数据库索引、搜索引擎优化和各种计算问题的解决。 首先,我们来看查找算法。查找是数据结构中...

    二分查找算法

    - 在排序算法中,例如快速排序和归并排序,也会用到二分查找。 通过理解二分查找算法的工作原理,熟练掌握其C++实现,并结合实际应用场景,我们可以有效地提高程序的运行效率。对于学习计算机科学的学生和专业...

    二分查找算法流程图流程图举例

    二分查找算法是计算机科学中的一个基本算法,适用于任何已排序的列表或数组。其优势在于能够快速地定位到目标值所在的范围,从而大幅减少不必要的比较次数。此外,对于大规模数据集而言,二分查找的效率远高于线性...

    计算机算法分析 二分查找 分治算法

    **二分查找与分治算法详解** 二分查找是一种基于分治策略的高效搜索算法,主要应用于有序数据集合。在给定的升序排列的数组a[0:n-1]中,二分查找的目标是找到特定元素x的位置,或者确认元素不在数组中。算法的基本...

    快速排序和二分查找

    【快速排序】是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。其基本思想是采用分治法,通过选取一个基准元素,将待排序序列分为两个子序列,使得一个子序列的所有元素都小于基准,另一个子序列...

    flash as3 二分查找动画演示

    二分查找(Binary Search)是计算机科学中一种高效的数据检索方法,适用于已排序的数组或列表。它的基本思想是将目标值与数组中间元素进行比较,如果目标值等于中间元素,则查找成功;如果目标值小于中间元素,则在...

    文件读出数组进行选择排序和二分查找(java)

    在Java编程中,文件读取、数组操作、选择排序以及二分查找是常见的编程任务,它们涉及了IO流、数据结构和算法等多个方面。以下是这些知识点的详细解释: 1. **文件读取**:Java提供了丰富的IO流类库用于读取文件。...

    查找排序算法应用

    4. **二分查找**: 实现了`bin_search`函数,用户输入待查找的学生学号,通过二分查找法定位学号位置,找到则输出相关信息,否则提示未找到。 5. **直接插入排序**: 直接插入排序是一种简单的排序算法,通过构建有序...

    MATLAB实现插入排序、二分归并排序、归并排序.rar

    不同之处在于,归并排序不使用二分查找,而是将数组分为两半,然后对每一半进行排序,再合并。归并排序在MATLAB中实现时,也需要递归地将数组划分为更小的部分,直到每个部分仅包含一个元素,然后逐步合并这些元素,...

    C# 经典排序算法大全和二分查找算法

    本资源“C#经典排序算法大全和二分查找算法”提供了多种经典的排序算法实现,以及C#中的二分查找算法。让我们深入探讨这些算法的原理、实现方式以及它们在实际开发中的应用。 首先,我们来看一下排序算法。排序是将...

    快速排序对数组排序,二分查找。

    快速排序是一种高效的排序算法,而二分查找则是一种在有序序列中寻找特定元素的有效方法。 快速排序由英国计算机科学家C.A.R. Hoare在1960年提出,它的基本思想是采用分治法。首先选择一个基准值,将数组分为两部分...

    算法分析与设计-实验二 二分查找实验报告.docx

    二分查找算法是一种高效的数据搜索方法,主要应用于已排序的序列。它的基本思想是通过不断地将待搜索区域减半来快速定位目标值。这个过程基于分治策略,将大问题分解为更小的子问题来解决。在二分查找算法中,每次...

    winform 二分查找算法源码

    在IT领域,二分查找算法(也称为折半查找)是一种高效的搜索算法,尤其适用于已排序的数据集合。这种算法利用了有序数据集的特点,通过不断缩小查找范围来快速定位目标值。在本案例中,"winform 二分查找算法源码" ...

    Java 二分查找 算法

    需要注意的是,二分查找的前提是数据必须有序,因此在实际应用中,通常需要先对数据进行排序,例如使用快速排序、归并排序等。此外,二分查找在大数据量时表现优异,适用于索引查找和数据库查询等领域。 二分查找...

    数据结构各种查找排序算法的实现

    本资料包涵盖了数据结构的各种查找排序算法的实现,以及相关的习题、试卷和答案,非常适合学习者深入理解和实践。 首先,让我们来看看查找算法。查找算法的目标是在数据集合中找到特定的元素。常见的查找算法有线性...

    C语言查找排序算法源码大全

    二分查找(非递归) &lt;*******\n"); printf("\t***********&gt; 3.二分查找(递归) &lt;*******\n"); printf("\t***********&gt; 4,直接插入排序 &lt;*******\n"); printf("\t***********&gt; 5.直接选择排序 &lt;*******\n"); ...

Global site tag (gtag.js) - Google Analytics