O(n) algorithm to find the median of n² implicit numbers

Question

Problem: input is a (not necessarily sorted) sequence S = k1, k2, ..., kn of n arbitrary numbers. Consider the collection C of n² numbers of the form min{ki,kj}, for 1 <=i, j<=n. Present an O(n) time and O(n) space algorithm to find the median of C.

So far I've found by examining C for different sets S that the number of instances of the smallest number in S in C is equal to (2n-1), the next smallest number: (2n-3) and so on until you only have one instance of the largest number.

Is there a way to use this information to find the median of C?

Answer 1

There are a number of possibilities. One I like is Hoare's Select algorithm. The basic idea is similar to a Quicksort, except that when you recurse, you only recurse into the partition that will hold the number(s) you're looking for.

For example, if you want the median of 100 numbers, you'd start by partitioning the array, just like in Quicksort. You'd get two partitions -- one of which contains the 50^th element. Recursively carry out your selection in that partition. Continue until your partition contains only one element, which will be the median (and note that you can do the same for another element of your choice).

Answer 2

Yes, good puzzle. We can find median developing on the lines you said.

In C we have 1 occurence of max(k), 3 occurrence of next highest, 5 of next highest and so on

1. If we ordered elements of C, number of elements on the left of mth highest number is m^2 (sum of odd numbers)

2. The numbers that we are interested in (to calculate median) a. If n is odd is (n^2+1)/2 = alpha b. If n is even then alpha1 = n^2/2 and alpha2 = n^2/2+1 but alpha1=n^2/2 is never a square number => the number immediately on the right of alpha1 is equal to alpha1 (sum of first m odd numbers is square) => alpha1=alpha2.

3. So it boils down to determining m such that m^2 (sum of first m odd numbers) is just higher than (n^2/2)

4. So it boils down to determining m=ceiling(n/sqrt(2) and mth highest number in original sequence. (Whether to find mth highest or (n-m-1)th lowest is optimization).

5. We can easily find mth highest number (just keep noting first m largest number from left) or use median of medians algortithm to do it in linear time.

Answer 3

Wikipedia has a good article on Selection algorithms. If you are using C++, the STL includes a nth_element() algorithm with linear time on average.