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.