= Lower weighted median
{title2=$\sum_{x_i<m}w_i<\tfrac12,\quad\sum_{x_i>m}w_i\leq\tfrac12$}
For ordered distinct values with positive weights summing to one, choose the first value whose cumulative weight reaches one half. The preceding cumulative weight is strictly below one half, and the remaining mass is at most one half, proving the displayed conditions. Stopping on equality chooses the lower value when a cumulative weight is exactly one half. Sorting followed by a scan takes $O(n\log n)$ time; <median of medians> partitioning with a residual weight target gives deterministic <linear time>.
Back to article page
