# Find a weighted median for unsorted array in linear time

For days, I'm trying to figure out, whether it is possible to find an item in array which would be kind of weighted median in linear time.

It is very simple to do that in exponential time.

So let's say that we have an array, each item of this array has 2 attributes - price and weight. The goal is to find an item x such that: SUM of weights of all items which costs less than x <= SUM(all items)/2 and SUM of weights of all items which costs more than x <= SUM(all items)/2.

If the array was sorted, it would be simple:

Go from the first item one by one, count sum and if the sum becomes greater that SUM(all items)/2, then you found desired item.

Could you give me some hint how to find such item in linear time?

• Why not first sort the array then do what you proposed in question. Or you are looking for algorithm to run precisely in O(n) time. – Prateek Apr 21 '16 at 13:56
• @Prateek "in linear time" in the question title does seem to imply that. – Tom van der Zanden Apr 21 '16 at 14:00

Let $A$ be an input array containing $n$ elements, $a_i$ the $i$-th element and $w_i$ its corresponding weight. You can determine the weighted median in worst case linear time as follows. If the array length is $\leq 2$, find the weighted median by exhaustive search. Otherwise, find the (lower) median element $a_x$ using the worst case $O(n)$ selection algorithm and then partition the array around it (using the worst case $O(n)$ partition algorithm from QuickSort). Now determine the weight of each partition. If weight of the left partition is $< \frac{1}{2}$ and weight of the right partition is $\leq \frac{1}{2}$ then the weighted (lower) median is $a_x$. If not, then the weighted (lower) median must necessarily lie in the partition with the larger weight. So, you add the weight of the "lighter" partition to the weight of $a_x$ and recursively continue searching into the "heavier" partition. Here is the algorithm's pseudocode (written in Latex).

FIND-WEIGHTED_LOWER_MEDIAN(A)
if $n$ == 1
return $a_1$
elseif $n$ == 2
if $w_1 \geq w_2$
return $a_1$
else
return $a_2$
else
determine $a_x$, the (lower) median of A
partition A around $a_x$
$W_{low}$ = $\sum\limits_{{a_i} < {a_x}} {{w_i}}$
$W_{high}$ = $\sum\limits_{{a_i} > {a_x}} {{w_i}}$
if $W_{low} < \frac{1}{2}$ AND $W_{high} \leq \frac{1}{2}$
return $a_x$
else if $W_{low} \geq \frac{1}{2}$
$w_x = w_x + W_{high}$
B = \{ a_i \in A: a_i \leq a_x \}
FIND-WEIGHTED_LOWER_MEDIAN(B)
else
$w_x = w_x + W_{low}$
B = \{ a_i \in A: a_i \geq a_x \}
FIND-WEIGHTED_LOWER_MEDIAN(B)


Now let's analyze the algorithm and derive its complexity in the worst-case. The recurrence of this recursive algorithm is $T(n) = T(\frac{n}{2} + 1) + \Theta(n)$. Indeed, we have no more than a recursive call on half the elements plus the (lower) median. The initial exhaustive search on up to 2 elements costs $O(1)$, determining the (lower) median using the select algorithm requires $O(n)$, and partitioning around the (lower) median requires $O(n)$ as well. Computing $W_{low}$ or $W_{high}$ is again $O(n)$. Solving the recurrence, we get the complexity of the algorithm in the worst case, which is $O(n)$.

Of course, a real implementation should not use the worst case $O(n)$ selection algorithm, since it is well known that the algorithm is not practical (it is of theoretical interest only). However, the randomized $O(n)$ selection algorithm works pretty well in practice and can be used since it's really fast.

• Can this algorithm be modified to find both the medians? – Abhijit Sarkar Nov 22 '18 at 1:44

You can do binary search for the price of x that satisfies the criterion. Computing the sum would take linear time each iteration (giving $O(n\log n)$ time) but you can compute the sum faster if you reuse work from previous iterations.

• @Torn Thank you for an advice. I understand the part with reusing work from previous iterations and in fact, I was thinking about binary search too. But I can't figure out what to search for because it's unsorted so If I choose some item, how to choose another in next iteration of binary search? For example if I have array - prices = [6,4,3,5,0,1,2] with weights = [10,20,30,15,5,10,20] – Milano Apr 21 '16 at 19:34
• You don't need the array to be sorted to do binary search, you just need to be able to find the element with the median price (out of the items remaining). – Tom van der Zanden Apr 21 '16 at 19:36
• Ok so: 1. Sum is 110, middle is 55. 2. Start with item on index 0, which is a price 6 with weight 10. And now I'm stucked, how to use binary search, what to search for? Thanks – Milano Apr 21 '16 at 20:11
• Another approach I was thinking about is to start with 1st item which is trivialy the result, then compute result adding next item etc. But it seems to be higher than linear. – Milano Apr 21 '16 at 20:16