Хомулло Степан Николаевич
10.12.2021 01:05 (6 д. 01:06)
[5889717]
template<class T, class It>
auto FindImplemented(T value, It begin_it, It end_it, std::random_access_iterator_tag) {
auto begin = begin_it;
auto end = end_it;
size_t size = std::distance(begin, end);
auto middle_it = begin + size / 2;
do {
if (size == 2) {
if (*middle_it == value)
return middle_it;
else
end = middle_it;
} else {
if (value < *middle_it)
end = middle_it + 1;
else
begin = middle_it;
}
size = std::distance(begin, end);
middle_it = begin + size / 2;
} while (size > 1);
if (*middle_it == value)
return middle_it;
return end_it;
}
template<class T, class It, class IteratorTag>
auto FindImplemented(T value, It begin_it, It end_it, IteratorTag) {
auto it = begin_it;
while (it != end_it) {
if (*it == value)
return it;
it++;
}
return it;
}
template<class T, class It>
auto Find(T value, It begin_it, It end_it) {
typedef typename std::iterator_traits<It>::iterator_category category;
return FindImplemented(value, begin_it, end_it, category());
}