# Find the median of two sorted arrays of different size in O(min(log(n),log(m)) complexity

Given two sorted arrays of length m,n, how do I find the median of the union of these two arrays in O(min(log(n),log(m)) time?

I've been trying to come up with an algorithm (and a proof) for several days. It's the same known question about finding the median of two sorted arrays but in O(min(log(n),log(m)) time insted of O(logm+logn). The arrays size may be different or equal (the solution should support both cases).

Here is the code I use:

int select(int *a, int *b, int sa, int sb, int k) {
int ma = sa < k/2 ? sa - 1 : k/2 - 1;
int mb = k - ma - 2;
if (sa + sb < k)
return -1;
if (sa == 0)
return b[k - 1];
if (sb == 0)
return a[k - 1];
if (k == 1)
return a[0] < b[0] ? a[0] : b[0];
if (a[ma] == b[mb])
return a[ma];
if (a[ma] < b[mb])
return select(a + ma + 1, b, sa - ma - 1, mb + 1, k - ma - 1);
return select(a, b + mb + 1, ma + 1, sb - mb - 1, k - mb - 1);
}

/*
median:
uses select to find the median of the union of a and b (where a and b are sorted
positive integer arrays of sizes sa and sb respectively).
*/
int median(int *a, int *b, int sa, int sb) {
int m1, m2;
if ((sa + sb) % 2 == 1)
return select(a, b, sa, sb, (sa + sb)/2 + 1);
return select(a, b, sa, sb, (sa + sb)/2);

}

int main() {
int a[3] = {2, 4, 6};
int b[11] = {1, 3, 5, 7, 13, 17, 22, 23, 24, 25, 31};
printf("\n median is %d\n", median(a, b, 3, 11));
return 0;
}

However I'm not sure if this code solves the problem correctly in O(min(log(n),log(m)) time. Is there a correct solution with this running time?

• Have you tried the $O(\log m + \log n)$ algorithm? Perhaps it already runs in time $O(\min(\log m + \log n))$. – Yuval Filmus May 6 '16 at 21:09
• Have you seen this similar question? Anyway, what is your question? You want to decode how the code you provided is working or get min(logn, logm) solution? – Evil May 8 '16 at 0:53
• Please ask only one question per question. I'm deleting the second question. For analyzing running time, please see meta.cs.stackexchange.com/questions/599/… – D.W. May 31 '16 at 21:37