Олейник Владислав Викторович
12.01.2022 17:27 (10 д. 01:04)
[5971208]
#pragma once
#include <iterator>
template<typename T, typename It, typename Tag>
It Find_(const T &value, It first, It last, Tag tag) {
for (; first != last; ++first) {
if (*first == value) {
return first;
}
}
return last;
}
template<typename T, typename It>
It Find_(const T &value, It first, It last, std::random_access_iterator_tag) {
It l = first;
It r = last;
while (l < r) {
It mid = l + (r - l) / 2;
if (value < *mid) {
r = mid;
} else {
l = mid + 1;
}
}
r--;
if (*r == value) {
return r;
}
return last;
}
template<typename T, typename It>
It Find(const T &value, It first, It last) {
return Find_(value, first, last,
typename std::iterator_traits<It>::iterator_category());
}