Median of 5 sorted arrays?

Question

I am trying to find the solution for median of 5 sorted arrays. This was an interview questions. The solution I could think of was merge the 5 arrays and then find the median [O(l+m+n+o+p)]. I know that for 2 sorted arrays of same size we can do it in log(2n). [by comparing the median of both arrays and then throwing out 1 half of each array and repeating the process]. .. Finding median can be constant time in sorted arrays .. so I think this is not log(n) ? .. what is the time complexity for this ? 1] Is there a similar solution for 5 arrays . What if the arrays are of same size , is there a better solution then ? 2] I assume since this was asked for 5, there would be some solution for N sorted arrays ? Thanks for any pointers. Some clarification/questions I asked back to the interviewer: Are the arrays of same length => No I guess there would be an overlap in the values of arrays => Yes As an exercise, I think the logic for 2 arrays doesnt extend . Here is a try: Applying the above logic of 2 arrays to say 3 arrays: [3,7,9] [4,8,15] [2,3,9] ... medians 7,8,3 throw elements [3,7,9] [4,8] [3,9] .. medians 7,6,6 throw elements [3,7] [8] [9] ..medians 5,8,9 ... throw elements [7] [8] [9] .. median = 8 ... This doesnt seem to be correct ? The merge of sorted elements => [2,3,4,7,8,9,15] => expected median = 7

Answer 1

Since the arrays are sorted, do a merge sort to get one final sorted list.

The median is the middle number UNLESS there is an even number of such statistics.

In that case, the median is the average of the two middle ones.

In your example, you have [3,7,9], [4,8,15], [2,3,9]

merging the first two arrays [ 3,4,7,8,9,15]

final merge with [2,3,9]

2,3,3,4,7,8,9,9,15

the median is 7.

Answer 2

Merge-sort the arrays

the median shall be the middle number

as long as you know how many are in each array, you can add them up.

the median is the middle number