#ifndef CPP_2_COURSE_FIND_H
#define CPP_2_COURSE_FIND_H

template<typename T, typename Iterator>
Iterator Find(const T &value, Iterator first, Iterator last) {
    using category = typename std::iterator_traits<Iterator>::iterator_category;
    if constexpr(std::is_same_v < category, std::random_access_iterator_tag >) {
        auto left = first;
        auto right = last;
        while (right - left > 1) {
            auto mid = left + (right - left) / 2;
            if (*mid < value)
                left = mid;
            else
                right = mid;
        }
        if (*left == value)
            return left;
        if (*(left + 1) == value)
            return (left + 1);
        return last;
    } else {
        while (first != last) {
            if (*first == value) {
                return first;
            }
            first++;
        }
        return last;
    }
}

#endif  // CPP_2_COURSE_FIND_H