#include <algorithm>
template <typename T, typename Iterator>
Iterator LinearSearch(const T&value, Iterator first, Iterator last) {
for (Iterator x = first; x != last; x++) {
if (value == *x) {
return x;
}
}
return last;
}
template<class T, class It>
auto FindImplemented(T value, It begin_it,
It end_it, std::random_access_iterator_tag) {
auto it = std::lower_bound(begin_it, end_it, value);
if (*it == value)
return it;
else
return end_it;
}
template<class T, class It, class IteratorTag>
auto FindImplemented(T value, It begin_it, It end_it, IteratorTag) {
return LinearSearch(value, begin_it, end_it);
}
template<class T, class It>
auto Find(T value, It begin_it, It end_it) {
typedef typename std::iterator_traits<It>::iterator_category category;
return FindImplemented(value, begin_it, end_it, category());
}