= Solution
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 \b[<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 \b[$O(n\log n)$ time].
Back to article page
