Here's one (untested). Suppose the two arrays are a and b and WLOG |a|
<= |b|.
First consider the "divide and conquer" step where |a| > 1 (and
therefore |b|>1 also). Let A be the middle element of a and B the
middle element of B.
Then there are two cases that let you throw away |a|-1 elements (remove
them from the problem):
(1) If A <= B, then throw away the bottom half of a (not including A)
and the same number of elements from the top of b.
(2) Otherwise throw away the top half of a and the same number of
elements from the bottom of b.
The O( log(|A| + |B|) ) performance follows because you eliminate at
least half of one or the other of the arrays at each step.
The base case of length zero for a is easy. Just find b's median.
The base case for |a|=1 is a little messy. I just plugged through all
possibilities. Some genius out there will probably find a cool way to
avoid this.
Note all the self-calls are tail recursive, so this is trivial to
re-implement with a loop.
double median_of_2(double *a, int na, double *b, int nb)
{
if (na > nb) // ensure a is no longer than b
return median_of_2(b, nb, a, na);
if (na == 0) // base case when a has zero length
return (nb % 2 != 0) ? b[nb/2] : (b[nb/2 - 1] + b[nb/2]) / 2;
if (na == 1) { // base case when a has length 1
if (nb == 1)
return (a[0] + b[0]) / 2;
else if (nb % 2 != 0) { // nb is odd
if (a[0] < b[nb/2 - 1])
return (b[nb/2 - 1] + b[nb/2]) / 2;
else if (b[nb/2 + 1] < a[0])
return (b[nb/2] + b[nb/2 + 1]) / 2;
else
return (a[0] + b[nb/2]) / 2;
}
else { // nb is even
if (a[0] < b[nb/2 - 1])
return b[nb/2 - 1];
else if (a[0] > b[nb/2])
return b[nb/2];
else
return a[0];
}
}
// general divide and conquer case
if (a[na/2] <= b[nb/2]) {
int n = na / 2;
return median_of_2(a + n, na - n, b, nb - n);
}
else {
int n = na - na / 2;
return median_of_2(a, na - n, b + n, nb - n);
}
}
