二分查找排序算法
程序员文章站
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)。虽以递归形式定义,但是尾递归,可改写为循环。
二分查找的优点和缺点:
二分查找只适用顺序存储结构。为保持表的有序性,在顺序结构里插入和删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
对那些查找少而又经常需要改动的线性表,可采用链表作存储结构,进行顺序查找。链表上无法实现二分查找。
五:高级思想
对于二分查找算法,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; 这样的话left与right的值比较大的时候,其和可能溢出。
陷阱2: 预防while循环时出现死循环。例如:
right = n;
while(left < right) {
…
right = middle;
…
}
如果搜索数组中不存在的数字的时候,可能会导致死循环,因为最后left = middle, right = middle + 1,这样每次更新left和middle总是不变的。
参考资料:
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
下一篇: 最长公共子序列问题