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:
Post a Comment