一:概念
二分查找又称折半查找(折半搜索/二分搜索),优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而 查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表 分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录, 使查找成功,或直到子表不存在为止,此时查找不成功。
二:原理
二分查找的基本思想是:(设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("没有找到");//表示没有找到 }
相关推荐
此资源是基本插入算法的改进版本,利用数学上的二分法能提高基本插入算法的效率,包括了实例讲解以及python代码实现(每行都有注释)
递归二分查找算法;
二分查找算法是运用分治的典型例子:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。所以容易设计出二分搜索算法:在 a[0] [1] [n-1] 中搜索 x, 找到x时返回其在数组中的位置,否则返回-...
二分查找(非递归) <*******\n"); printf("\t***********> 3.二分查找(递归) <*******\n"); printf("\t***********> 4,直接插入排序 <*******\n"); printf("\t***********> 5.直接选择排序 <*******\n"); ...
c语言实现查找排序算法应用,1.掌握查找的不同方法,并能用高级语言实现查找算法。 2.熟练掌握顺序表和有序表的顺序查找和二分查找方法。 3.掌握排序的不同方法,并能用高级语言实现排序算法。 4.熟练掌握...
通过快速排序对java对象集进行升序排序且随之进行十分查找
查找算法:二分查找、顺序查找的实现 参见博客:http://blog.csdn.net/xiaowei_cqu/article/details/7748260
排序算法、二分查找、二叉树查找
用C#实现的经典排序算法汇总大全,以及调用方法和C#实现的二分查找算法.
数据结构八大算法,详细介绍了算法的如何实现,以及编码过程,有简单到复杂,由浅入深,看看会有很大收获。
算法:还有比二分查找更快的算法,判断是否是子字符串IsSubsequence,排序算法数据结构 最快的排序算法
该工具包含有Java一些比较常见的排序算法和查找算法。 排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数...查找算法包括:线性查找、二分查找、插值查询、斐波那契(黄金分割法)、
包括顺序查找、二分查找、选择排序、冒泡排序,二分排序,插入排序,希尔排序,堆排序,归并排序等
自己看书时写的算法:快速排序、二分查找 CPP文件
编写程序构造一个有序表La,从键盘接收一个关键字key,用二分查找法在La 中查找key,若找到则提示查找成功并输出key所在的位置,否则提示没有找到信息。 2.编写程序实现Hash表的建立、删除、插入以及查找操作。 ...
本资源包括一份分治法算法分析文档,4份Java源程序,包括二分查找、归并排序、快速排序、比赛日程安排。
在已排序好的数组T中运用二分查找的方法查找目标数的位置。 根据实验要求和伪码信息,用二分查找的方法在输入的排序好的数组T中查找目标数的位置。若目标数在数组中输出下标位置,不在则输出零。
二叉排序树:更新二叉排序树、查找结点、插入结点、删除结点、中序输出排序树 、返回 查找算法:顺序查找、二分查找、二插排序树、返回
该程序是我写的博客“一起talk C栗子吧(第二十五回:C语言实例-二分查找)”的配套程序,共享给大家使用
多种排序查找算法的java实现源码,包括选择排序,冒泡排序,改进版冒泡排序,二分查找,归并排序等等