Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 5 / d / i

Keep each weight attached to its value while sorting, then return the first cumulative weight reaching one half:

weightedMedian(A, weights):
    R = records (A[i], weights[i], i), sorted by first component
    cumulative = 0
    for (value, weight, original_index) in R:
        cumulative = cumulative + weight
        if cumulative >= 1/2:
            return original_index

All weights are positive, so the cumulative weights strictly increase. At the returned entry the mass strictly to its left is below one half, while the mass strictly to its right is at most one half. This is the lower weighted median, including the exact equality case: stop at the earlier value whose cumulative mass is exactly one half. Sorting takes $O(n\log n)$ and the scan takes $O(n)$, giving $O(n\log n)$ time.