//二分查找法
//注意：[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);
}
