Median of Two Sorted Arrays

11 Dec 2011

Given 2 sorted arrays, n and m in length, find the median.

First, let's just assume that the numbers are unique and (n+m) is odd.

The first obvious solution that comes to me takes O(n).

We use 2 pointers starting on the beginning of each array. We walk them one at a time in increasing order. If we have walk (n+m)/2 times, then the latest touched element is the median.

Anyway, on, it states that the solution should take only O(log(m+n)).

Ok…. O(log(m+n)) requires some sort of binary search.

Anyway, let's make some random observations as I always do.

Observation 1

If we combine the two arrays and keep the order, the median is at the ((n+m+1)/2)th.

Observation 2

Let's throw out some examples:

1 3 5 7 9 11 13 2 4 6 8 10 12 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 7 8 9 5 6 10 11 12 13

What we can do with O(log n) is to pick one element in the first array and find the lesser elements in the second array.

Observation 3

Let's say we pick the element x-th from the first array. We only need to consider the first (((n+m)/2) - x) elements in the second array.

This observation is something. We pick the element i-th in the first array, say a[i], and we find all the lesser elements in the second array. Let's say b[j] is the biggest element that is less than a[i].

  • if (i+j) == (n+m)/2, then we got the answer.
  • if (i+j) > (n+m)/2, then we try again with the (i/2)-th element.
  • If (i+j) < (n+m)/2, then we try again with the (i + (n-i)/2)-th element.

You know, the binary search algorithm. You need to refine the algorithm, a little.