频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
二分查找的递归与非递归
2016-09-07 09:42:17         来源:刘二阳的博客  
收藏   我要投稿

之前写过二分查找的代码,但一直没有总结。今天就先总结一下二分查找的递归与非递归的实现。

一、关于二分查找的算法

1.二分查找的条件:必须是一组有序的数据(升序或降序)

2.二分查找也称折半查找,其算法就是(以一组升序的数据来解释):

a.每次先找出这组数据的中间数(mid);

b.如果要查找的数据(num)小于 mid ,那么就在前一半数据中查找;如果要查找的数据(num)大于 mid ,那么就在后一半数据中查找;

c.继续重复上述步骤,直到找到为止,此时返回数据的位置;找不到返回空。很明显,这样就大大提高了查找的效率。

可以用这幅图简单来表示一下:

\

举个例子:例如要在数组a={1,2,3,4,5,6,7,8,9}中查找 2 这个数,那么就要先找出中间数 5 ,由于 2<5 ,那么应该在该数据的前一半(1~5)查找,然后继续重复上述工作...

 

二、代码实现

非递归:

 

//非递归
int bin_search(int *arr,int sz,int num)
{
	assert(arr);
	int left = 0;	//每段数据的左端
	int right = sz-1;	//每段数据的
	int mid = 0;
	while (left <= right) 
	{
		mid = (left+right)/2;	//中间位置每次都在变
		if (num == *(arr+mid))
		{
			return mid;
		}
		else if (num < *(arr+mid))
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
		
	}
	if(left > right)
		return NULL;
	else
		return mid;
}
递归:

 

 

//递归
int bin_search(int* arr, int left, int right, int num)
{
	assert(arr);
	int mid = 0;
	while (left <= right)
	{
		mid = (left + right)/2;
		if (num == *(arr+mid))
		{
			return mid;
		}
		else if (num < *(arr+mid))
		{
			return(bin_search(arr,left,mid,num));
		}
		else
		{
			return(bin_search(arr,mid,right,num));
		}
	}
	return NULL;
}
点击复制链接 与好友分享!回本站首页
相关TAG标签 递归
上一篇:Scala Cookbook翻译 Chapter 1.Strings 第三部分
下一篇:二进制十六进制转十进制基础.
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站