4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Have you tried the $O(\log m + \log n)$ algorithm? Perhaps it already runs in time $O(\min(\log m + \log n))$. $\endgroup$ – Yuval Filmus May 6 '16 at 21:09
  • 2
    $\begingroup$ 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? $\endgroup$ – Evil May 8 '16 at 0:53
  • $\begingroup$ 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/… $\endgroup$ – D.W. May 31 '16 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.