Median of an unsorted array variation for 12.11

#1

Hi,
The median for a sequence with odd length appears straightforward( ie: say sequence size is 11 median is the 6th largest element).
So it would appear the median of an even sequence could be computed by doing this twice(For example find the 5th and 6th largest for a sequence of size 10).
Or is there a better way?

0 Likes
#2

Hey @pdny,

Thanks for this question, because years ago I was thinking that as well. However, the answer is probably NO since the selection algorithm can only guarantees the element at i-th position is exactly the i-th largest (or smallest) element, the elements at its left are greater (or less) than the one on i-th, and the elements at its right are less (or greater) than the one on i-th. Since we want to find 5th and 6th in the example of even number of elements; we have to perform this twice.

Thinking from the complexity side, it makes no difference since the complexity is still O(n), where n is the number of elements. In practice, probably sorting (with complexity O(nlogn)) might run faster.

0 Likes