2
$\begingroup$

I want to compute the median in an array of size $m$ which consists of distinct integers from $\{0, 1, ..., n-1\}$, I have $m<n$. By median I mean the middle element (rounding up/down if the array size is even) in the sorted version of the array.

Ideally, the expected number of passes over the array should be $\mathcal{O}(\log{}n)$, the used memory should be $\mathcal{O}(\log{}n)$ bits and the solution should be exact. I'm flexible with the time complexity as long as it's feasible.

Since finding the median in an unsorted array is such a common problem I expected to quickly find some solution which suits my needs but after some research I'm wondering if this is even possible. Does anyone know a solution or where I could expect to find one?

$\endgroup$
4
$\begingroup$

The natural algorithm determines the $\log n$ bits of the median, MSB to LSB. Suppose that we have determined the $k$ MSBs of the median, $b_{m-1},\ldots,b_{m-k}$. Determine the number of integers in the array whose $k+1$ MSBs are $b_{m-1},\ldots,b_{m-k},1$, and use this to find the $(k+1)$th MSB of the median.

This algorithm uses $O(\log n)$ passes and $O(\log m + \log n) = O(\log n)$ space.

$\endgroup$
  • $\begingroup$ How would you "use this to find the $(k+1)$th MSB of the median."? $\endgroup$ – Anna Vopureta Oct 13 '17 at 14:35
  • $\begingroup$ I'll let you figure that out. $\endgroup$ – Yuval Filmus Oct 13 '17 at 14:38
0
$\begingroup$

As @Yuval Filmus pointed out, you can use a histogram approach.

Since you know the number of integers and that they are all distinct you immediately know the rank. Now you create 2 histograms/buckets, one for all integers whose MSB is 0 the other one for 1's. By the number of elements in the buckets you can conclude in which one the median must be. You have effectively found the MSB of the median, simply repeat this procedure for the rest of the bits.

A Java implementation which does this can be found here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.