How to find the average of the upper half of the N numbers?

Question

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

Answer 1

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

Then just go through the array and sum all the elements that are larger than the median.

Indicate the number of items you have summed up ( M). If M < N/2, then this means that several elements that are equal to the average value (namely, N/2 - M) belong to the upper half. Add to your sum that many median values. We need this complexity because we do not know how many median elements (there may be several) belong to the upper half: if we take all of them, we can eventually summarize more elements N/2.

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

Answer 2

. , , , n. n/2 .

, , O(n log n) , O(1) O(log n).

, O (n), , .

Answer 3

, , , . , . ., , wikipedia .

Answer 4

:

Use Quicksort, select some core. This will split your list into two sub-lists, one smaller than the reference, one larger than this. If the size of the smaller sublist is <= N / 2, calculate the average a1.
If size == N/2 or size == N/2 -1
  you do it immediately.

If you do not redo the large sublist, until the total size is equal to N / 2.

If size> N / 2 is shared by a smaller sublist.

Repeat all the way to the end.

PS: you do not need to sort.