leetcode: Median of Two Sorted Arrays

Problem Description:

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution and Precautions:

(1) compare the middle of the two sorted array, and we can discard half of the search space every time. If theA[mid] < B[mid] then the first half of A and the second half of B could be discarded, why? You can think about it

The total time would be O(log m + n).

(2) the more popular approach which is also less tricky to implement is by finding k-th element among the two sorted arrays. That is, find the (m+n) / 2 -th element among A and B if m + n is odd, if m + n is even, find (m+n) / 2-th and (m+n) / 2 + 1-th element, and get the median of these two elements.

To find the k-th element among sorted array A of m elements and B of n elements, we keep invariant i + j = k – 1 where i is the index in A and j for B. If we keep i + j = k -1. And we do the following

if( A[i-1] <= B[j] <= A[i]) return B[j] since before B[j] there are exactly A[0]…A[i-1] i elements plus, B[0] …[j-1] j elements, that is there are exactly i + j = k – 1 elements, then B[j] is of course the k-th elements;

Similar if (B[j-1] <= A[i] <= B[j] ) return A[i]

In other cases, we just check if (A[i] <= B[j]) or not, if it is true, we know it must be A[i] < B[j-1] why? because otherwise, we already return A[i] previously. Now that, A[i] < B[j-1], we know A[0]…A[i] won’t be the k-th element because these are TOO SMALL, they are only among the first k – 1 smallest elements. And B[j]…B[n-1]a are also not possible, because they are TOO LARGE. Because they are at least larger than j + i + 1 = k elements. so they are at lest t (t > k)  -th elemnet.

Similarly, when A[i] > B[j], we have A[i-1] > B[j], and A[i] with the larger portion could be discarded, and B[j] with the smaller portion could be discarded.

(3) There is a MIT solution by binary searching the target A[i] and check if it is less than or equal or larger than the median in constant time.

However, if you check that manual out, essentially, it still follows that i + j = k – 1 sort of things where k  might be (m+n)/2.

Tips and Divergent thinking:

It is too tricky to make the code correct for this problem. (2) might be a better choice to code it right and code it clearly.

Written on June 12, 2013