Finding Median in Three Sorted Arrays in O(logn)

Question

By googling for minutes, I know the basic idea.

1. Let A,B,and C be sorted arrays containing n elements.
2. Pick median in each array and call them medA, medB, and medC.
3. Without loss of generality, suppose that medA > medB > medC.
4. The elements bigger than medA in array A cannot become the median of three arrays. Likewise, the elements smaller than medC in array C cannot, so such elements will be ignored.
5. Repeat steps 2-4 recursively.

My question is, what is the base case? Assuming a lot of base cases, I tested the algorithm by hands for hours, but I was not able to find a correct base case. Also, the lengths of three arrays will become different every recursive step. Does step 4 work even if the length of three arrays are different?

Answer 1

This algorithm works for two sorted arrays of same sizes but not three. After the one iteration, you eliminates half of the elements in A and C but leaves B unchanged, so the number of elements in these arrays are no longer the same, and the method no longer apply. For arrays of different sizes, if you apply the same method, you will be removing different number of elements from the lower half and upper half, therefore the median of the remaining elements is not the same as the median of the original arrays.

That being said, you can modify the algorithm to eliminate same number of elements at both end in each iteration, this could be in efficient when some of the arrays are very small and some are very large. You can also turn this into a question of finding the k-th element, track the number of elements being throw away and change value of k at each iteration. Either way this is much trickier than the two array situation.

There is another post talking about a general case: Median of 5 sorted arrays

Answer 2

I think you can use the selection algorithm, slightly modified to handle more arrays.

You're looking for the median, which is the p=[n/2]^th element.

Pick the median of the largest array, find for that value the splitting point in the other two arrays (binary search, log(n)). Now you know that the selected number is the kth (k = sum of the positions).

If k > p, discard elements in the 3 arrays above it, if smaller, below it (discarding can be implemented by maintaing lower and upper indexes for each array, separately). If it was smaller, also update p = p - k.

Repeat until k=p.

Oops, I think this is log(n)^2, let me think about it...