#include<iterator>
template<typename T, typename Iterator>
Iterator FindImpl(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 FindImpl(const T &value,
Iterator first_,
Iterator last_,
std::random_access_iterator_tag) {
auto last = last_;
last--;
while (first_ < last) {
Iterator mid = (last - first_) / 2 + first_;
if (*mid < value) {
first_ = mid + 1;
} else {
last = mid;
}
}
if (*first_ == value) {
return first_;
}
return last_;
}
template<typename T, typename Iterator>
Iterator Find(const T &value, Iterator first_, Iterator last_) {
return FindImpl(value,
first_,
last_,
typename std::iterator_traits<Iterator>::iterator_category());
}