// Binary search (lower_bound, upper_bound, equal_range, binary_search).
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);//求取整个区间的长度len
_Distance __half;
_ForwardIter __middle;//定义区间的中间迭代器
while (__len > 0) {//若区间不为空，则在区间[first,last)开始查找value值
__half = __len >> 1;//向右移一位，相当于除以2，即取区间的中间值
__middle = __first;//middle初始化为区间的起始位置
advance(__middle, __half);//middle向后移half位，此时middle为区间的中间值
if (*__middle < __val) {//将value值与中间值比较，即是二分查找,若中间值小于value，则继续查找右半部分
//下面两行令first指向middle的下一个位置
__first = __middle;
++__first;
__len = __len - __half - 1;//调整查找区间的长度
}
else
__len = __half;//否则查找左半部分
}
return __first;
}
//在已排序区间[first,last)查找value值
//若该区间存在与value相等的元素，则返回指向第一个与value相等的迭代器
//若该区间不存在与value相等的元素，则返回指向第一个不小于value值的迭代器
//若该区间的任何元素都比value值小，则返回last
/*
函数功能：Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.
函数原型：
default (1) ：版本一采用operator<比较
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val);
custom (2) ：版本二采用仿函数comp比较规则
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
*/
//版本一
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));
}
template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val, _Compare __comp, _Distance*)
{
_Distance __len = 0;
distance(__first, __last, __len);//求取整个区间的长度len
_Distance __half;
_ForwardIter __middle;//定义区间的中间迭代器
while (__len > 0) {//若区间不为空，则在区间[first,last)开始查找value值
__half = __len >> 1;//向右移一位，相当于除以2，即取区间的中间值
__middle = __first;//middle初始化为区间的起始位置
advance(__middle, __half);//middle向后移half位，此时middle为区间的中间值
if (__comp(*__middle, __val)) {//若comp判断为true，则继续在右半部分查找
//下面两行令first指向middle的下一个位置
__first = __middle;
++__first;
__len = __len - __half - 1;//调整查找区间的长度
}
else
__len = __half;//否则查找左半部分
}
return __first;
}
//版本二：
template <class _ForwardIter, class _Tp, class _Compare>
inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val, _Compare __comp) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES_SAME_TYPE(_Tp,
typename iterator_traits<_ForwardIter>::value_type);
__STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);
return __lower_bound(__first, __last, __val, __comp,
__DISTANCE_TYPE(__first));
}
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);//求取整个区间的长度len
_Distance __half;
_ForwardIter __middle;//定义区间的中间迭代器
while (__len > 0) {//若区间不为空，则在区间[first,last)开始查找value值
__half = __len >> 1;//向右移一位，相当于除以2，即取区间的中间值
__middle = __first;//middle初始化为区间的起始位置
advance(__middle, __half);//middle向后移half位，此时middle为区间的中间值
if (__val < *__middle)//若value小于中间元素值
__len = __half;//查找左半部分
else {
//下面两行令first指向middle的下一个位置
__first = __middle;
++__first;
__len = __len - __half - 1;//更新len的值
}
}
return __first;
}
//在已排序区间[first,last)查找value值
//返回大于value值的第一个元素的迭代器
/*
函数功能：Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.
函数原型：
default (1) ：版本一采用operator<比较
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val);
custom (2) ：版本二采用仿函数comp比较规则
template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
*/
//版本一
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));
}
template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val, _Compare __comp, _Distance*)
{
_Distance __len = 0;
distance(__first, __last, __len);
_Distance __half;
_ForwardIter __middle;
while (__len > 0) {
__half = __len >> 1;
__middle = __first;
advance(__middle, __half);
if (__comp(__val, *__middle))
__len = __half;
else {
__first = __middle;
++__first;
__len = __len - __half - 1;
}
}
return __first;
}
//版本二
template <class _ForwardIter, class _Tp, class _Compare>
inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val, _Compare __comp) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES_SAME_TYPE(_Tp,
typename iterator_traits<_ForwardIter>::value_type);
__STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);
return __upper_bound(__first, __last, __val, __comp,
__DISTANCE_TYPE(__first));
}
//函数举例
/*
#include <iostream> // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector> // std::vector
int main () {
int myints[] = {10,20,30,30,20,10,10,20};
std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
std::vector<int>::iterator low,up;
low=std::lower_bound (v.begin(), v.end(), 20); // ^
up= std::upper_bound (v.begin(), v.end(), 20); // ^
std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
std::cout << "upper_bound at position " << (up - v.begin()) << '\n';
return 0;
}
Output:
lower_bound at position 3
upper_bound at position 6
*/
