How to find average of top half of N numbers?

Question

Given N arbitrary integers, how to find average of top half of these numbers? Is there an O(n) solution? If not is it possible to prove that it's not possible?

Answer 1

First, find a median of the given array (it takes linear time).

Then, just walk through array and sum up all elements that are greater than the median.

Count how many elements you summed (M). If M < N/2, then it means that several elements that are equal to the median value (namely, N/2 - M) belong to the top half. Add to your sum that many median values. We need this complexity because we don't know how many median elements (there can be several) belong to the top half: if we take them all, we can end up having summed more than N/2 elements.

Now you have the sum of the top half of the array. Divide by N/2, and you're done.