• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

c语言实现的通用二分查找算法

OC/C/C++ 水墨上仙 1404次浏览

c语言实现的通用二分查找算法
作者:wallwind
来源:http://blog.csdn.net/wallwind/article/details/8272141

//
/*
	二分查找是基于排好序的算法。复杂度低,并且很高效,
	由于项目中大量使用的了二分查找,但是又不能每个业务实现一个
	因此有必要实现一个通用的二分查找
	其主要思想:通过对已经排好序的数组,进行数据指针的比较。
	
	@const void *key 需要查找的key值
	@const void *base, 所要查找数据的首地址
	@int nmemb,所要查找的成员数量
	@int size, 每个元素的大小
	@int *piEqual,是否能查找到的标志查到为1,否则为0
*/
int bsearch_int (const void *key, const void *base, int nmemb, int size, int *piEqual)
{
	size_t l, u, idx;
	const void *p, *p2;
	int comparison, comparison2;
	*piEqual = 0;
	if (nmemb < 0) return -1;
	if (!nmemb) return 0;
	l = 0;
	u = nmemb;
	while (l < u)
	{
		idx = (l + u) / 2;
		p = (void *) (((const char *) base) + (idx * size));
		comparison = *(int *)key - *(int *)p ;
		if (comparison == 0)
		{
			*piEqual = 1;
			return idx;
		}		
		else if (comparison < 0)
		{
			if (idx == 0) return idx;
			p2 = (void *) (((const char *) base) + ((idx - 1) * size));
			comparison2 = *(int *)key - *(int *)p2 ;
			if (comparison2 > 0) return idx;
			u = idx;
		}
		else /*if (comparison > 0)*/ 
		{
			l = idx + 1;
		}		
	}
	return u;
}


喜欢 (0)
加载中……