#include<iterator>
template<typename T, typename Iterator>
Iterator FindImpl(const T& value, Iterator first, Iterator last, std::random_access_iterator_tag){
auto if_no = 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 if_no;
}
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 Find(const T& value, Iterator first, Iterator last){
return FindImpl(value, first, last, typename std::iterator_traits<Iterator>::iterator_category());
}