二分查找

二分查找

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

转自:http://www.cppblog.com/converse/archive/2009/10/05/97905.html

二分查找算法基本思想
二分查找算法的前置条件是,一个已经排序好的序列(在本篇文章中为了说明问题的方便,假设这个序列是升序排列的),这样在查找所要查找的元素时,首先与序列中间的元素进行比較,假设大于这个元素,就在当前序列的后半部分继续查找,假设小于这个元素,就在当前序列的前半部分继续查找,直到找到同样的元素,或者所查找的序列范围为空为止.

用伪代码来表示, 二分查找算法大致是这个样子的:

left = 0, right = n -1


while (left <= right)

    mid = (left + right) / 2

    
case

        x[mid] < t:    left = mid + 1;

        x[mid] = t:    p = mid; 
break;

        x[mid] > t:    right = mid -1;

return -1;





第一个正确的程序


依据前面给出的算法思想和伪代码, 我们给出第一个正确的程序,可是,它另一些小的问题,后面会讲到

int search(
int array[], 
int n, 
int v)

{

    
int left, right, middle;

    left = 0, right = n – 1;

    
while (left <= right)

    {

        middle = (left + right) / 2;

        
if (array[middle] > v)

        {

            right = middle;

        }

        
else 
if (array[middle] < v)

        {

            left = middle;

        }

        
else

        {

            
return middle;

        }

    }

    
return -1;

}





以下,讲讲在编写二分查找算法时可能出现的一些问题.




边界错误造成的问题


二分查找算法的边界,一般来说分两种情况,一种是左闭右开区间,类似于[left, right),一种是左闭右闭区间,类似于[left, right].须要注意的是, 循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,假设循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.假设两者不一致,会造成程序的错误.比方以下就是错误的二分查找算法:

int search_bad(
int array[], 
int n, 
int v)

{

    
int left, right, middle;

    left = 0, right = n;

    
while (left < right)

    {

        middle = (left + right) / 2;

        
if (array[middle] > v)

        {

            right = middle – 1;

        }

        
else 
if (array[middle] < v)

        {

            left = middle + 1;

        }

        
else

        {

            
return middle;

        }

    }

    
return -1;

}



这个算法的错误在于, 在循环初始化的时候,初始化right=n,也就是採用的是左闭右开区间,而当满足array[middle] > v的条件是, v假设存在的话应该在[left, middle)区间中,可是这里却把right赋值为middle – 1了,这样,假设恰巧middle-1就是查找的元素,那么就会找不到这个元素.

以下给出两个算法, 各自是正确的左闭右闭和左闭右开区间算法,能够与上面的进行比較:

以下这两个算法是正确的

int search2(
int array[], 
int n, 
int v)

{

    
int left, right, middle;

    left = 0, right = n – 1;

    
while (left <= right)

    {

        middle = (left + right) / 2;

        
if (array[middle] > v)

        {

            right = middle – 1;

        }

        
else 
if (array[middle] < v)

        {

            left = middle + 1;

        }

        
else

        {

            
return middle;

        }

    }

    
return -1;

}

int search3(
int array[], 
int n, 
int v)

{

    
int left, right, middle;

    left = 0, right = n;

    
while (left < right)

    {

        middle = (left + right) / 2;

        
if (array[middle] > v)

        {

            right = middle;

        }

        
else 
if (array[middle] < v)

        {

            left = middle + 1;

        }

        
else

        {

            
return middle;

        }

    }

    
return -1;

}





死循环


上面的情况还仅仅是把边界的当中一个写错, 也就是右边的边界值写错, 假设两者同一时候都写错的话,可能会造成死循环,比方以下的这个程序:

int search_bad2(
int array[], 
int n, 
int v)

{

    
int left, right, middle;

    left = 0, right = n – 1;

    
while (left <= right)

    {

        middle = (left + right) / 2;

        
if (array[middle] > v)

        {

            right = middle;

        }

        
else 
if (array[middle] < v)

        {

            left = middle;

        }

        
else

        {

            
return middle;

        }

    }

    
return -1;

}



这个程序採用的是左闭右闭的区间.可是,当array[middle] > v的时候,那么下一次查找的区间应该为[middle + 1, right], 而这里变成了[middle, right];当array[middle] < v的时候,那么下一次查找的区间应该为[left, middle – 1], 而这里变成了[left, middle].两个边界的选择都出现了问题, 因此,有可能出现某次查找时始终在这两个范围中轮换,造成了程序的死循环.




溢出


前面攻克了边界选择时可能出现的问题, 以下来解决还有一个问题,事实上这个问题严格的说不属于算法问题,只是我注意到非常多地方都没有提到,我认为还是提一下比較好.


在循环体内,计算中间位置的时候,使用的是这个表达式:

middle = (left + right) / 2;



假如,left与right之和超过了所在类型的表示范围的话,那么middle就不会得到正确的值.


所以,更稳妥的做法应该是这种:

middle = left + (right – left) / 2;



更完好的算法


前面我们说了,给出的第一个算法是一个”正确”的程序, 可是另一些小的问题.


首先, 假设序列中有多个同样的元素时,查找的时候不见得每次都会返回第一个元素的位置, 比方考虑一种极端情况:序列中都仅仅有一个同样的元素,那么去查找这个元素时,显然返回的是中间元素的位置.


其次, 前面给出的算法中,每次循环体中都有三次情况,两次比較,有没有办法降低比較的数量进一步的优化程序?


<<编程珠玑>>中给出了解决这两个问题的算法,结合前面提到溢出问题我对middle的计算也做了改动:

int search4(
int array[], 
int n, 
int v)

{

    
int left, right, middle;

    left = -1, right = n;

    
while (left + 1 != right)//这个循环维持的条件是
left<right && array[left]<v<=array[right],所以到最后的时候,

    {//
假设能够找到目标,则仅仅剩下两个数,而且满足 
array[left]<v<=array[right],
是要查找的数是right

        middle = left + (right - left) / 2;

        
if (array[middle] < v)//
必须保证
array[left]<v<=array[right],所以left = middle;

        {//
假设left =middle+1,则有可能出现 array[left]<=v的情况

            left = middle;

        }

        
else

        {

            right = middle;

        }

    }

    
if (right >= n || array[right] != v)

    {

        right = -1;

    }

    
return right;

}


这个算法是全部这里给出的算法中最完好的一个,正确,精确且效率高.

可是这个算法的还是不能非常好的理解

能够用以下的算法,能够找出满足条件的数


int Bi_Search(int a[],int n,int b)//
{//返回等于b的第一个
	if(n==0)
		return -1;
	int low = 0;
	int high = n-1;
	int last = -1;//用last记录上一次满足条件的下标
	while (low<=high)
	{
		int mid = low +(high-low)/2;
		if (a[mid]==b)
		{
			last = mid;
			high = mid -1;
		}
		else if(a[mid]>b)
			high = mid -1;
		else
			low = mid +1;
	}

	return last;

}
int Bi_Search1(int a[],int n,int b)//大于b的第一个数
{
	if(n<=0)
		return -1;
	int last = -1;
	int low = 0;
	int high = n-1;
	while (low<=high)
	{
		int mid = low +(high - low)/2;
		if(a[mid]>b)
		{
			last = mid;
			high = mid -1;
		}
		else if (a[mid]<=b)
		{
			low =mid +1;
		}
	}

	return last;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118473.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 华为模拟器ensp怎么安装_ensp模拟器网页版

    华为模拟器ensp怎么安装_ensp模拟器网页版华为模拟器说实话有时候真的是很烦人,总是莫名其妙的出问题,而且网上教程一般也解决不了因此我认为学会ensp的重装真的很重要,因此只要我们删除干净了,安装最多花不了20分钟的时间接下来我就来说说怎么安装华为ensp模拟器—————————————————————————–…

    2022年10月14日
  • madvr怎么设置hdr_文字识别软件

    madvr怎么设置hdr_文字识别软件PotPlayer播放HDR视频截图PotPlayer播放HDR视频截图Windows10内置视频播放器播放HDR视频Windows10内置视频播放器播放HDR视频从去年开始,支持HDR的电视机已经卖得铺天盖地,支持4KUHDHDR的片源也变得丰富起来,动辄50GB的视频资源让广大10TB级松鼠病晚期患者们兴奋地表示家里屯的硬盘和百兆宽带终于有了用武…

  • 详解Java中的Spring框架

    详解Java中的Spring框架详解Spring什么是SpringSpring的优点Bean容器Bean的注解Bean属性Bean作用域Bean的生命周期Bean的实例化IoC(InversionofControl)和DI(DedendencyInjection)IoC(控制反转)DI(依赖注入)AOP什么是SpringSpring是分层的JavaSE/EEfull-stack轻量级开源框架,以IoC(InverseofControl,控制反转)和AOP(AspectOrientedProgramming

  • Idea使用git切换远程分支[通俗易懂]

    描述公司开发人数越来越多,项目业务逻辑越来越复杂,就有了越来越多的分支,各个小伙伴在各自的分支上进行开发,然后进行合并,如果本大爷需要切换到别的开发分支上,那如何实现呢?解决方案屁话不多说,直接上图 点击鼠标右键,选择GIT–&gt;Repository–&gt;Pull… Branchestomerge:选择你需要的分支,如果你没遇到你想要的分支就点击刷新一下。…

  • C语言标准库函数大全(ctype、time 、stdio、stdlib、math、string)

    C语言标准库函数大全(ctype、time 、stdio、stdlib、math、string)文章目录C语言函数库一.C语言函数库一.<assert.h>二.<ctype.h>三.<errno.h>四.<limits.h>五.<locale.h>六.<math.h>七.<setjmp.h>八.<signal.h>九.<stdarg.h>十.<stddef.h>十一.<stdio.h&.

  • js 图片加载失败处理方法「建议收藏」

    js 图片加载失败处理方法「建议收藏」个人github:https://github.com/qiilee 欢迎follow在项目中不可避免会用到图片,尤其是列表,有时候图片会加载失败;这样就会显示一个很难看的坏图片缩略图;下面介绍两种方法,解决这个问题:1、如果在你的项目中有引入jQuery插件,你可以使用error([[data],fn])这个函数;$("img").error(function(){  //当图…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号