Я видел на Cppreference.com реализацию std::lower_bound
, которая выглядит следующим образом https://en.cppreference.com/w/cpp/algorithm/lower_bound:
template<class ForwardIt, class T>
ForwardIt LowerBound(ForwardIt first, ForwardIt last, const T& value)
{
ForwardIt it;
typename std::iterator_traits<ForwardIt>::difference_type count, step;
count = std::distance(first, last);
while (count > 0) {
it = first;
step = count / 2;
std::advance(it, step);
if (*it < value) {
first = ++it;
count -= step + 1;
}
else
count = step;
}
return first;
}
Но я могу реализовать ее так же, как бинарный поиск;если найденное значение возвращает его итератор, в противном случае возвращает первый итератор (который больше его):
Я сделал это, и он отлично работает:
template<typename T, typename U>
T Lower_Bound(T first, T last, const U& val) {
while (first != last) {
auto mid = first + ((last - first) / 2);
if (val < *mid)
last = mid;
else
if (val > *mid)
first = mid + 1;
else
return mid;
}
return first;
}
Теперь он работает нормальноно я не уверен в этом, а также CppReference
лучше, чем моя реализация?