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_indexAll 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 and the scan takes , giving time.
Maintain a residual cumulative-weight target , initially , while discarding whole partitions. Choose pivots by an ordinary median of the current entries, not by their weights:
selectWeighted(S, t):
if |S| == 1: return the sole record of S
p = deterministic unweighted median by value in S
L = records with value < p.value
R = records with value > p.value
ell = sum of weights in L
if t <= ell:
return selectWeighted(L, t)
if t <= ell + p.weight:
return p
return selectWeighted(R, t - ell - p.weight)
answer = selectWeighted(all records, 1/2)The invariant is , with the desired answer the first cumulative weight reaching inside the current ordered subset. The first branch uses
<=, which is essential: if the target equals the total left mass, the answer is the largest appropriate left-side value, not the pivot. The other branches preserve the residual target by subtracting exactly the mass discarded on the left.A median of medians routine finds the exact unweighted median in deterministic linear time. Partitioning and summing also take linear time, and each recursive call retains at most entries. Therefore . The algorithm is worst-case linear, not merely expected linear under a random pivot. Exact comparisons to the weight threshold are assumed; floating-point rounding at exactly one half would need explicit treatment.
Articles by others on the same topic
There are currently no matching articles.