欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL之binary_search

程序员文章站 2022-05-05 19:09:31
...
//二分查找法
//注意:[first,last)是已排序
//同样也有两个版本
/*
函数功能:Returns true if any element in the range [first,last) is equivalent to val, and false otherwise.
函数原型:
default (1)	:版本一默认operator<
	template <class ForwardIterator, class T>
	bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val);
custom (2)	:版本二采用仿函数comp
	template <class ForwardIterator, class T, class Compare>
	bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);
*/
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);//调用二分查找函数,并返回不小于value值的第一个迭代器位置i
  return __i != __last && !(__val < *__i);
}

template <class _ForwardIter, class _Tp, class _Compare>
bool binary_search(_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);
  _ForwardIter __i = lower_bound(__first, __last, __val, __comp);//调用二分查找函数,并返回不小于value值的第一个迭代器位置i
  return __i != __last && !__comp(__val, *__i);
}