template <typename TEdge, typename TFunc, typename... TArgs>
TEdge left_bin_search(
    TEdge lhs,
    TEdge rhs,
    TFunc&& check_func,
    TArgs&&... extra_parameters)
{
    while (lhs != rhs)
    {
        auto mid = (rhs + lhs) / 2;
        if (check_func(mid, std::forward<TArgs>(extra_parameters)...))
        {
            rhs = mid;
        }
        else
        {
            lhs = mid + 1;
        }
    }
    return lhs;
}

template <typename TEdge, typename TFunc, typename... TArgs>
TEdge right_bin_search(
    TEdge lhs,
    TEdge rhs,
    TFunc&& check_func,
    TArgs&&... extra_parameters)
{
    while (lhs != rhs)
    {
        auto mid = (rhs + lhs + 1) / 2;
        if (check_func(mid, std::forward<TArgs>(extra_parameters)...))
        {
            lhs = mid;
        }
        else
        {
            rhs = mid - 1;
        }
    }
    return lhs;
}

double find_median_of_parts(const std::vector<int>& part1, const std::vector<int>& part2)
{
    auto get_median = [](auto lhs, auto rhs) -> double
    {
        if (rhs == lhs)
        {
            return -1;
        }

        auto mid = (rhs - lhs) / 2;
        if ((rhs - lhs) % 2 == 1)
        {
            return *(lhs + mid);
        }
        return (*(lhs + mid) + *(lhs + mid - 1)) / 2.;
    };

    auto check_lbs = [](size_t checking_offset, double median, auto begin)
    {
        return std::isgreater(*(begin + checking_offset), median);
    };

    auto check_rbs = [](size_t checking_offset, double median, auto begin)
    {
        return std::islessequal(*(begin + checking_offset), median);
    };

    auto Is_doubles_equal = [](double lhs, double rhs)
    {
        return fabs(lhs - rhs) <= std::numeric_limits<double>::epsilon();
    };

    for (auto start_1 = part1.begin(), end_1 = part1.end(), start_2 = part2.begin(), end_2 = part2.end();;)
    {
        if (end_1 - start_1 == 1 && end_2 - start_2 == 1)
        {
            return (*start_1 + *start_2) / 2.;
        }

        auto med_1 = get_median(start_1, end_1);
        auto med_2 = get_median(start_2, end_2);

        if (Is_doubles_equal(med_1, -1))
        {
            return med_2;
        }
        if (Is_doubles_equal(med_2, -1))
        {
            return med_1;
        }

        if (Is_doubles_equal(med_1, med_2))
        {
            return med_1;
        }
        if (std::isless(med_1, med_2))
        {
            start_1 += left_bin_search(0l, end_1 - start_1 - 1, check_lbs, med_1, start_1);
            if (!check_lbs(start_1 - part1.begin(), med_1, part1.begin()))
            {
                start_1 = end_1;
            }

            end_2 = start_2 + right_bin_search(0l, end_2 - start_2 - 1, check_rbs, med_2, start_2) + 1;
        }
        else
        {
            start_2 += left_bin_search(0l, end_2 - start_2 - 1, check_lbs, med_2, start_2);
            if (!check_lbs(start_2 - part2.begin(), med_2, part2.begin()))
            {
                start_2 = end_2;
            }

            end_1 = start_1 + right_bin_search(0l, end_1 - start_1 - 1, check_rbs, med_1, start_1) + 1;
        }
    }
}