async_v1

template <typename RandomAccessIterator, typename Value>
RandomAccessIterator LowerBound(const execution::sequenced_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 auto middle = left_bound + (right_bound - left_bound) / 2;
        if (*middle < value) {
            left_bound = middle;
        } else {
            right_bound = middle;
        }
    }
    if (left_bound == range_begin && !(*left_bound < value)) {
        return left_bound;
    } else {
        return right_bound;
    }
}

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) {
    if (range_end - range_begin == 1) {
        return range_begin;
    }
    if (range_end - range_begin == 2) {
        return *range_begin < value ? range_begin : range_end;
    }
    // размер 2-х поддиапазонов
    size_t size_one_third = (range_end - range_begin) / 3;
    const RandomAccessIterator middle_left = range_begin + size_one_third;
    const RandomAccessIterator middle_right = middle_left + size_one_third;
    future<bool> is_first_one_third = async([middle_left, &value] {
        return !(*middle_left < value); }); // false - левая часть нас не интересует
    bool is_second_one_third = !(*middle_right < value);
    //future<bool> no_is_second_one_third = async([middle_right, &value] {
    //    return *middle_left < value; });

    if (is_first_one_third.get()) {
        return LowerBound(range_begin, middle_left, value);
    } else if (is_second_one_third) {
        return LowerBound(middle_left, middle_right, value);
    } else {
        return LowerBound(middle_right, range_end, value);
    }
}