LowerBound

#include <algorithm>
#include <execution>
#include <future>

using namespace std;

template <typename RandomAccessIterator, typename Value>
RandomAccessIterator LowerBound(const execution::sequenced_policy&, RandomAccessIterator range_begin, RandomAccessIterator range_end, const Value& value) {
    return lower_bound(range_begin, range_end, value);
}

template <typename RandomAccessIterator, typename Value>
RandomAccessIterator LowerBound(RandomAccessIterator range_begin, RandomAccessIterator range_end, const Value& value) {
    return LowerBound(execution::seq, range_begin, range_end, value);
}

template <typename RandomAccessIterator, typename Value>
RandomAccessIterator LowerBound(const execution::parallel_policy&, RandomAccessIterator range_begin, RandomAccessIterator range_end, const Value& value) {
    auto left_bound = range_begin;
    auto right_bound = range_end;
    while (left_bound + 1 < right_bound) {
        const int distance = right_bound - left_bound;
        const int part_length = max(1, distance / 3);
        const auto middle_left = left_bound + part_length;
        const auto middle_right = right_bound - part_length;

        auto left_less_future = async([middle_left, &value] { return *middle_left < value; });

        if (*middle_right < value) {
            left_bound = middle_right;
        } else if (left_less_future.get()) {
            left_bound = middle_left;
            right_bound = middle_right;
        } else {
            right_bound = middle_left;
        }
    }
    if (left_bound == range_begin && !(*left_bound < value)) {
        return left_bound;
    } else {
        return right_bound;
    }
}