Finding the median in a combined array of two sorted arrays

Question

Suppose we have 2 sorted arrays of integers with sizes n and m. What is the best way to find the median of all numbers m + n?

This is easy to do with complexity log(n) * log(m). But I want to solve this problem in log(n) + log(m)time. So is there a suggestion to solve this problem?

Answer 1

Explanation

The key point of this problem is to ignore half A and B of each step recursively, comparing the median of the remaining A and B:

if (aMid < bMid) Keep [aMid  +1 ... n] and [bLeft ... m]    
else Keep [bMid + 1 ... m] and [aLeft ... n]
// where n and m are the length of array A and B

As the following: time complexity O(log(m + n))

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length, n = B.length;
    int l = (m + n + 1) / 2;
    int r = (m + n + 2) / 2;
    return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
}

public double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
    if (aStart > A.length - 1) return B[bStart + k - 1];            
    if (bStart > B.length - 1) return A[aStart + k - 1];                
    if (k == 1) return Math.min(A[aStart], B[bStart]);

    int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
    if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; 
    if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1];        

    if (aMid < bMid) 
        return getkth(A, aStart + k / 2, B, bStart, k - k / 2); // Check: aRight + bLeft 
    else 
        return getkth(A, aStart, B, bStart + k / 2, k - k / 2); // Check: bRight + aLeft
}

, ! , .

Answer 2

, Java Stack Overflow. K K + 1 , K .

Kth , :

• Kth Kth + 1 X Y

Kth ; (, )

• X , K- X Y K- Y

• , K == 2, X Y X Y (min (X [0], Y [0]))

• ;

  . A - min ( (X), K/2)

  II. B - min ( (Y), K/2)

  III. X [A] > Y [B], 1. X, Y ' Y B Y K' = K - B, X ' X A X, Y K '= K - A

, , Python, , , " " .

Answer 3

A a. a B. b1 b2 ( B , , b, , ). b1 & leq; a & leq; b2, a . , .

a , b2, A B . B , . a , b1, A B . log (n) ( , , , ).

, . , B. , , A B. log (m). 2 * (log (n) + log (m)) , log (n) + log (m).

, , , iehrlich, .

Answer 4

, . , A B, A, , , B . , A+B. .

, . , |A| + |B| . , (, , , ). , , , (|A| + |B| - 1) / 2 . A x A ( i). , x B[j] < x < B[j+1], i + j == (|A| + |B| - 1) / 2, x .

- O(log(max(|A|, |B|)) O(1) .