Thursday, April 15, 2010

Find Median of Two Sorted Arrays

See here for the following 3 methods:
Method 1: similar to merge sort, the (m+n)/2-th element is median. O(m+n).
Method 2: divide and conquer. O(log(n)) time, O(1) space. This works when m = n.
Method 3: binary search. O(log(n)) time, O(1) space. This works when m = n.

When m != n, it's more complicated. Can method 3 be extended to this case? Can have a try. Another possible way is to append the shorter array by INT_MIN (or value less than min of both arrays) and INT_MAX (or value greater than max of both arrays), then apply previous method.

If n >> m, can use binary search possibly.

A similar problem is finding the k-th largest element in a union of two arrays. See idea here. It's O(log(n+m)). This can be specialized to the situation of finding median, where k = (m+n)/2.

No comments:

Blog Archive

Followers