Возможно ли реализовать std :: lower_bound в терминах бинарного поиска? - PullRequest
0 голосов
/ 08 октября 2019

Я видел на 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 лучше, чем моя реализация?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...