Exercise 9.3.8
2n elements, we know that the length is an even number and we're looking for a lower median. We need to observe that the median we're looking for is between the medians of the two arrays. Let's elaborate on that.
Let's assume that the median is at positionk in array A . This means that there are k−1 elements less than the median in A and n−k elements greater than the median in B . If k<n/2 then the median of A will be greater than the final median, but the median of B will be lesser than it. It's the other way around for k≥n/2 . Thus the median of the two arrays is always between the medians of each.
Step 3 removes the same number of elements from each array, half of which are greater than the median and half of which are less than it. This reduces the subproblem to two smaller arrays that are sorted and their elements have the same median.
https://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/algorithm/i2a_ex_9.3-8/ex9_3_8.cpp
http://rxwen.blogspot.com/2009/12/ex-93-8-of-introduction-to-algorithms.html
Read full article from Exercise 9.3.8
LetThis was fun!X[1..n] andY[1..n] be two arrays, each containingn numbers already in sorted order. Give anO(lgn) -time algorithm to find the median of all2n elements in arraysX andY .
- If the two arrays are of length
1 , we pick the lower of the two elements - We the two medians of the array
- We take the lower part of the array with the greater median and the upper part of the array with the lesser median. If each array has
n elements, we take the first/last⌊n/2⌋ elements - We solve the problem for the new arrays
Let's assume that the median is at position
Step 3 removes the same number of elements from each array, half of which are greater than the median and half of which are less than it. This reduces the subproblem to two smaller arrays that are sorted and their elements have the same median.
def two_array_median(a, b): if len(a) == 1: return min(a[0], b[0]) m = median_index(len(a)) i = m + 1 if a[m] < b[m]: return two_array_median(a[-i:], b[:i]) else: return two_array_median(a[:i], b[-i:]) def median_index(n): if n % 2: return n // 2 else: return n // 2 - 1https://code.google.com/p/clrs/source/browse/ch09/9.3-8.py
def find_median(A, B, lo, hi): |
n = len(A) |
if hi - lo <= 0: return None |
k = (lo + hi) // 2 |
left = B[n-k-2] if n-k-2 >=0 else -1 |
rigt = B[n-k-1] |
if left <= A[k] <= rigt: |
return A[k] |
elif A[k] > rigt: |
return find_median(A, B, lo, k) |
else: |
return find_median(A, B, k + 1, hi) |
def two_array_median(A, B): |
n = len(A) |
med = find_median(A, B, 0, n) |
if med is None: |
med = find_median(B, A, 0, n) |
return med |
int getMedian(const int_vector& x, int lx, int hx, const int_vector& y, int ly, int hy) |
{ |
int cx, cy, mx, my, z = 0; |
cx = (lx+hx)/2; |
cy = hy-(cx-lx); |
mx = x[cx]; |
my = y[cy]; |
if(mx <= my) |
{ |
if(cy < 1 || mx >= y[cy-1]) |
return mx; |
else |
return getMedian(x, cx+1, hx, y, ly, cy-1); |
} |
else |
{ |
if(cx < 1 || my >= x[cx-1]) |
return my; |
else |
return getMedian(x, lx, cx-1, y, cy+1, hy); |
} |
} |
Read full article from Exercise 9.3.8