STL中的二分查找

STL中使用二分查找的来进行搜索的函数有以下3个：

- upper_bound

- lower_bound

- binary_search

[STL]upper_bound

默认形式：
template<class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val);

客制化形式:
template<class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

功能：在一个已排序的序列中[first, last)，返回第一个大于val的元素所在的地址。如果未找到结果，则返回last,该函数使用二分查找实现;

实现:

template<class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val)
{
	ForwardIterator it;
	iterator_traits<ForwardIterator>::differnce_type count, step;
	count = std::distance(first, last);
	while(count > 0)
	{
		it = first; step = (count >> 1); std::advance(it, step);
		
		if(!(val < *it))
		{
			first = ++it; count -= step + 1;
		}
		else
		{
			count = step;
		}
	}
	
	return first;
}

[STL]lower_bound
默认形式:
template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val);

客制化形式：
template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

功能： 在一个已排序的序列[first, last), 返回第一个大于等于val元素的地址,如未找到，则返回last；

实现：

template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val)
{
	ForwardIterator it;
	iterator_traits<ForwardIterator>::difference_type count, step;
	
	count = std::distance(first, last);
	
	while(count > 0)
	{
		it = first; step = (count >> 1); std::advance(it, step);
		
		if(!(val <= *it))
		{
			first = ++it; count -= step + 1;
		}
		else
		{
			count = step;
		}
	}
}

[STL]binary_search

默认形式：
template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val)；

客制化形式：
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val, Compare comp)；

功能:在一个已排序的序列[first, last)中， 判断val是否存在;

实现：

template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val)
{
	ForwardIterator it = lower_bound(first, last, val);
	
	return ((it != last) && !(val < *it));
}