2

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?

user1885433
  • 313
  • 5
  • 13
  • When all three arrays' lengths are smaller than a constant, you can brute-force to find the median. It is also possible that two of arrays are length one but you cannot ignore the elements in the third array. In this case, you can modify binary search to find the median. – Yu-Han Lyu Sep 09 '13 at 13:49

2 Answers2

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

Community
  • 1
  • 1
Chen Pang
  • 1,370
  • 10
  • 11
0

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...

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176