#include<iterator>
template<typename T, typename Iterator>
Iterator FindTempl(const T &value,
Iterator first,
Iterator last,
std::random_access_iterator_tag) {
auto last_iter = last;
--last;
while (first < last) {
Iterator m = (last - first) / 2 + first;
if (*m == value) {
return m;
}
if (*m < value) {
first = m + 1;
} else {
last = m - 1;
}
}
return last_iter;
}
template<typename T, typename Iterator>
Iterator FindTempl(const T &value,
Iterator first,
Iterator last,
std::bidirectional_iterator_tag) {
while (first != last) {
if (*first == value) {
return first;
}
++first;
}
return last;
}
template<typename T, typename Iterator>
Iterator Find(const T &value, Iterator first, Iterator last) {
return FindTempl(value,
first,
last,
typename std::iterator_traits<Iterator>::iterator_category());
}