Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 算法 » ,

STL中的二分查找

二分查找的原理非常简单,但写出的代码中很容易含有很多Bug,二分查找一文中讲解过如何实现不同类型的二分查找,但是否一定要自己去实现二分查找呢?答案显然是否定的,本文将讲解STL中与二分查找有关函数的具体使用方法及其实现原理。

函数使用

STL中与二分查找相关的函数有4个,分别是lower_bound, upper_bound, equal_range和binary_search,下面通过一个简单的例子说明各个函数的使用方法。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int a[6] = {1, 2, 2, 2, 3, 4}; //已排序
	vector<int> v(a, a + 6);

	typedef vector<int>::iterator It; //迭代器类型
	It st = v.begin(), ed = v.end();  //起始迭代器

	It p1 = lower_bound(st, ed, 2);//>=2的第一个位置
	printf("%d\n", p1 - st);       // 1

	It p2 = upper_bound(st, ed, 2);//>2的第一个位置
	printf("%d\n", p2 - st);       // 4

	pair<It, It> p = equal_range(st, ed, 2);        //==2的位置
	printf("%d-%d\n", p.first - st, p.second - st); // 1-4

	bool exist = binary_search(st, ed, 2); //2是否存在
	printf("%d\n", exist);                 //1 (是)
}

其中每个函数实现的功能如下:

  • binary_search:查找某个元素是否出现。
  • lower_bound:查找第一个大于或等于某个元素的位置。
  • upper_bound:查找第一个大于某个元素的位置。
  • equal_range:查找某个元素出现的起止位置。注意,终止位置为最后一次出现的位置加一。

其中lower_bound和upper_bound的功能可能比较别扭,可以这样看:对于已排序的数组1 2 2 2 3 4,元素2出现了3次,第一次出现的位置为1,最后一次的位置为3,lower_bound即为这个第一次出现的位置,而upper_bound本意是要标志最后一次出现的位置,但STL中习惯使用左闭右开的区间,于是upper_bound返回的结果应该为最后一次出现的位置的下一个位置。当查找的元素一次都未出现时,二者返回的结果都是第一个大于该元素的位置。

函数实现

下面我们具体看每个函数的实现细节。我们这里使用的仍然是SGI 版本的STL,具体版本为v3.3。

lower_bound

lower_bound查找第一个大于或等于某个元素val的位置,根据二分查找,首先找到中间位置的元素mid,然后,

  • 如果mid < val,显然mid本身及其左边的元素都不可能是答案了,则把first置为 mid + 1。
  • 如果mid >= val,答案可能是mid本身或者mid左边的元素,则把last置为mid。

基本思想就是这样,但STL实现中使用的是迭代器,而迭代器不一定能随机访问,于是它需要使用distance函数计算迭代器间的距离,使用advance函数或者自增、自减运算实现迭代器的前进和后退。另外STL实现中没有在循环中使用first和last,而是使用了等价的first和len,这样可以方便非随机访问的迭代器求取中间值。

STL的实现中lower_bound函数本身只是进行了一系列的类型安全性检查,真正的工作放到了__lower_bound函数中进行。使用额外辅助函数的另一个目的是在辅助函数中添加模板类型_Distance,可以根据模板参数推导机制得到迭代器的距离类型,从而利用这个类型定义变量。

另外,STL的实现有两个版本,其中一个使用默认的比较函数<,第二个可以自定义比较方法comp,这里为了简洁,只提供了第一个版本的实现。本质上第二个版本实现中也只是把使用第一个版本中<进行比较的地方换成调用comp方法进行比较,并没有实质上的区别。
以下的每个函数都是如此,不再重复。

下面是具体的实现代码。

template <class _ForwardIter, class _Tp, class _Distance>
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Distance*) 
{
	_Distance __len = 0;
	distance(__first, __last, __len);
	_Distance __half;
	_ForwardIter __middle;

	while (__len > 0)
	{
		__half = __len >> 1;
		__middle = __first;
		advance(__middle, __half); //middle位置
		if (*__middle < __val)
		{
			__first = __middle;
			++__first;
			__len = __len - __half - 1;
		}
		else
			__len = __half;
	}
	return __first;
}

template <class _ForwardIter, class _Tp>
inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
{
	__STL_REQUIRES(_ForwardIter, _ForwardIterator);
	__STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
	__STL_REQUIRES(_Tp, _LessThanComparable);
	return __lower_bound(__first, __last, __val, __DISTANCE_TYPE(__first));
}

upper_bound

upper_bound的实现思路跟上面lower_bound类似,只是上面lower_bound是找大于或等于的,这里是找大于的。得到mid位置的元素后,

  • 如果mid <= val,显然mid本身及其左边的元素都不可能是答案了,则把first置为 mid + 1。
  • 如果mid > val,则答案可能是mid本身或者mid左边的元素,把last置为mid。

下面是代码实现。

template <class _ForwardIter, class _Tp, class _Distance>
_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Distance*)
{
	_Distance __len = 0;
	distance(__first, __last, __len);
	_Distance __half;
	_ForwardIter __middle;

	while (__len > 0)
	{
		__half = __len >> 1;
		__middle = __first;
		advance(__middle, __half);
		if (__val < *__middle)
			__len = __half;
		else
		{
			__first = __middle;
			++__first;
			__len = __len - __half - 1;
		}
	}
	return __first;
}

template <class _ForwardIter, class _Tp>
inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
{
	__STL_REQUIRES(_ForwardIter, _ForwardIterator);
	__STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
	__STL_REQUIRES(_Tp, _LessThanComparable);
	return __upper_bound(__first, __last, __val, __DISTANCE_TYPE(__first));
}

equal_range

equal_range查找某个元素出现的起止位置,可以通过以上的lower_bound和upper_bound函数实现。STL中也正是通过这两个函数实现,不过调用之前先进行进行普通二分查找找到第一个出现的位置mid后,

  • 在[first, mid)中调用lower_bound查找开始位置。注意,如果该区间没有找到的话,lower_bound会返回最后的位置mid,而mid此时正是开始位置。
  • 在[mid+1, last)中调用lower_bound查找结束位置,这里的last即为first + len。

具体的代码实现如下。

template <class _ForwardIter, class _Tp, class _Distance>
pair<_ForwardIter, _ForwardIter> __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Distance*)
{
	_Distance __len = 0;
	distance(__first, __last, __len);
	_Distance __half;
	_ForwardIter __middle, __left, __right;

	while (__len > 0)
	{
		__half = __len >> 1;
		__middle = __first;
		advance(__middle, __half);
		if (*__middle < __val)
		{
			__first = __middle;
			++__first;
			__len = __len - __half - 1;
		}
		else if (__val < *__middle)
			__len = __half;
		else
		{
			__left = lower_bound(__first, __middle, __val);   //[first, mid)查找起点
			advance(__first, __len);
			__right = upper_bound(++__middle, __first, __val);//[mid+1, last)查找终点
			return pair<_ForwardIter, _ForwardIter>(__left, __right);
		}
	}
	return pair<_ForwardIter, _ForwardIter>(__first, __first);
}

template <class _ForwardIter, class _Tp>
inline pair<_ForwardIter, _ForwardIter> equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
{
	__STL_REQUIRES(_ForwardIter, _ForwardIterator);
	__STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
	__STL_REQUIRES(_Tp, _LessThanComparable);
	return __equal_range(__first, __last, __val,__DISTANCE_TYPE(__first));
}

binary_search

binary_search查找某个元素是否出现,是最普通的二分查找。STL的实现中使用了lower_bound查找第一个大于或等于该元素的位置,如果该位置的元素同时也是小于或等于目标元素的,则说明该位置的元素确实等于目标元素,查找成功。否则查找失败。

template <class _ForwardIter, class _Tp>
bool binary_search(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
{
	__STL_REQUIRES(_ForwardIter, _ForwardIterator);
	__STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
	__STL_REQUIRES(_Tp, _LessThanComparable);
	_ForwardIter __i = lower_bound(__first, __last, __val);         //i上的数大于或等于目标元素
	return __i != __last && !(__val < *__i); //lower_bound查找成功 && i上的数小于或等于目标元素
}
上一篇: 下一篇:
  1. 提问:哪一个瞬间让你真的下定决心减肥了?知乎用户:那天班上一帅气的男生骑自行车带我,我一坐上去车翘起来了。

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论