Selecting median of two sorted arrays

In this post, I’d like to discuss one interesting algorithm problem which took me quite a while to find an ideal solution. The problem is as followings:

Array A and B are sorted with length of m and n respectively. Try to select median of the two arrays within O(log(m+n)) time. For example,

A = { 1, 4, 6, 10, 18 } B = { 1, 7, 13, 45, 58, 69, 100, 180, 300 } Answer: 13

Step1: The lengths are equal. Let us start with a special scenario of the problem. The solution is as following.

Examine the middle element of each array, and throw out the lower half of the array with the smaller element (since all those must be less than ½ the numbers) and throw out the upper half of the array with the larger element (since all those must be greater than ½ the numbers). Now both arrays are still the same size. Repeat until you have two elements left. This is your median. Each step, you eliminate half of the numbers, so it should have a runtime of O(logn).

Step2: What if the lengths are not equal?

The smartest solution I’ve found is padding. It is best to think of median as a special case of the select problem, where given a set and an index k, you need to find the kth smallest element. Median is simply Select(n/2) when n is even, and fully defined by Select(\floor(n/2)) and Select (\Ceiling(n/2)) when n is odd. Now there is a simple O(log n) algorithm for the Select problem on the union of two equal sorted arrays, that throws out the appropriate halves of the two lists recursively.

If you want a simpler reduction to equal sized lists, pad the shorter list with an equal number of positive and negative infinities. If you need an odd number of pads (ie: when the source lists have an odd total), do it with positive infinity and (since the set size was odd) return the lesser of the two retuned values.

Comments

• Anonymous
  September 21, 2008
  PingBack from http://www.easycoded.com/select-median-of-two-sorted-arrays/
• Anonymous
  January 23, 2009
  Sir in the above example when 10 is left in the first array and 7,13 is left in the second array then how do u apply the recursion means applying recursion does not decrease the size of sample
• Anonymous
  January 23, 2009
  Good catch. How about this?IF( (arrayA size + arrayB size)>3 ){    run_above_algo();}ELSE{   pick_up_median_manually();}
• Anonymous
  September 01, 2009
  Step1: The lengths are equal.We've two arrays of the same length. That means the total sum of elements is even, hence we've two medians. They may be, no doubt in one of the two arrays, and the other may not have a median for both at all.You have described how to find 2 numbers, which are suspected to be medians. However, perhaps one of them is not median at all(if both are in one array). We need to determinate which one of the two, surely is the median.