I've seen on Cppreference.com the implementation of std::lower_bound which looks like this 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;
}
But I can implement it just like a Binary Search; if the value found return its iterator otherwise return the first iterator (which is just greater than it):
I've done this and it works fine:
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;
}
Now it works fine but I am not sure of it, also is the CppReference's better than my implementation?
Aucun commentaire:
Enregistrer un commentaire