#pragma once

#include <iterator>

template<typename T, typename Iterator>
Iterator Find(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, \
                std::random_access_iterator_tag) {

    Iterator end = last;
    while (first != last) {
        Iterator mid = first + (std::distance(first, last) / 2);
        *mid < value ? first = mid + 1 : last = mid;
    }
    if (*last == value) {
        return last;
    }
    return end;
}

template<typename T, typename Iterator>
Iterator Find(const T& value, Iterator first, Iterator last) {
    typedef typename std::iterator_traits<Iterator>\
                        ::iterator_category it_category;
    return Find(value, first, last, it_category());
}