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.
Thursday, April 15, 2010
Subscribe to:
Post Comments (Atom)
Blog Archive
-
▼
2010
(67)
-
▼
April
(14)
- Find median
- Find Median of Two Sorted Arrays
- Online Algorithm Resources
- Max submatrix problem
- Check Equality of Two Number Sets
- Largest rectangle in histogram problem
- IR Evaluation
- Garbage collector implementation
- Find prime numbers
- Newton Ralphson's method to calculate square root
- The Frobenius Number
- Search in a circular sorted array
- The Maximal Rectangle Problem
- Young Tableau
-
▼
April
(14)
No comments:
Post a Comment