mardi 8 octobre 2019

Is it possible to implement std::lower_bound in terms of a binary search?

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