This answer is very similar to Massimo's except with a (hopefully) simpler style/structure of phrasing it and in addition includes the solution to find the second weighted median as well.
If you want just a hint, just look at step 1), and read no further. If you want more hints, continue to next step.
Assumptions:
Input is in two different arrays: Prices[], and Weights[]
Whenever values in Prices[] are rearranged, values in Weights[]
are also rearranged to keep the correspondence between indexes.
Approach:
1. Using the method from either Randomized selection, or Deterministic selection
algorithm, partition the Prices around a selected Pivot element.
2. Calculate the sum of all weights in the Left Partition as L, and the sum of
all weights in the Right Partition as R.
3. Let P be a 'reference' to the weight of the Pivot element.
4. Calculate the total weight of all the elements, L + P + R as S
5. a) If L > S/2:
P += R (Add weight of all elements in right partition to the Pivot)
Change array upper bound to end at Pivot element.
go to step 1.
b) Else If R > S/2:
P += L (Add weight of all element in left partition to the Pivot)
Change array lower bound to begin at the Pivot element.
go to step 1.
c) Else:
Pivot is the Median.
i) If L + P == S/2:
Successor of the Pivot element is also a Median.
Linear scan the Right partition to find the element with Min Price
as the Successor.
ii) Else If P + R == S/2:
Predecessor of the Pivot element is also a Median.
Linear scan the Left partition to find the element with Max Price
as the Predecessor.
return the Medians
(Done)
Correctness:
Step 5.a)
If L > S/2, the median cannot be in the Right Partition.
Because, if it be so, L will only get larger and violate the requirement that L must be less than or equal to S/2.
Hence, we look for median in the Left Partition
Step 5.b)
If R > S/2, the median cannot be in the Left Partition.
Because, if it be so, R will only get larger and violate the requirement that R must be less than or equal to S/2.
Hence, we look for median in the Right Partition
Step 5.c.i)
L + P <= S/2 implies R = S/2 and L + P = S/2, because L + P + R = S.
Step 5.c.ii)
P + R <= S/2 implies L = S/2 and P + R = S/2, because L + P + R = S.
Complexity:
The number of elements scanned to calculate L, and R is no more than the number of elements scanned to partition the array in each iteration/reduction.
Hence, the complexity of the solution is same as that of the Selection algorithm used, which is average O(n) if Randomized selection, or worst case O(n) if Deterministic selection is chosen.
In addition, 5.c.i) or 5.c.ii) do a one time scan of a maximum of n-1 elements in case there is a possibility for a second median, which doesn't add significantly to already deduced overall complexity of either average or worst case O(n)
Notes:
The approach is easy to implement in a non recursive way, and i also have some notes not though totally relevant to the question, but could be relevant to many people who end up here: https://thoughtvalve.blogspot.com/2020/03/why-only-2-weighted-medians-at-most.html