There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

We can solve this problem with the algorithm: Finding the Kth element in two sorted arrays. It’s quite straight forward. For example, supposing the total length of two arrays is N. If N is an odd number, we need to find the (N + 1) / 2 th number in two arrays, otherwise we need to find N / 2 th and (N + 1) / 2 th number and return the average of them.

The question requires a solution of O(log(m + n)) complexity. So we cannot do a linear search in these two arrays. But we can use a solution which is very similar to binary search.

For example, assuming we have the following two sorted arrays.

In this solution, we use mid = length / 2 to calculate the mid point position. The mid element of array A is A[3], and the mid element of array B is B[3]. We can divide each of them into two parts:

A_1(A[0], A[1], A[2]), A_2(A[3], A[4], A[5])

B_1(B[0], B[1], B[2]), B_2(B[3], B[4], B[5]).

Now we can compare A[3] with B[3]. If A[3] <= B[3], we know that the second part of B is equal or larger than any elements in the first part of A and B. We want the K th element in these two arrays. We have two situation here.

1. If K is smaller than the length of A_1 and B_1, we know that this element should not be in B_2. So we can throw this part and continue searching K th element in A and B_1.
2. If K is larger than the length of A_1 and B_1, K th element is not in A_1. Otherwise K will be smaller than the sum of length of A_1 and B_1. And then we can continue searching K – B_1.length th element in A_2 and B.

It’s quite similar for the situation A[3] > B[3]. The code is as follow.

 1 public class Solution { 2     public double findMedianSortedArrays(int A[], int B[]) { 3         int lengthA = A.length; 4         int lengthB = B.length; 5         if ((lengthA+lengthB)%2 == 0) { 6             double r1 = find(A, 0, lengthA, B, 0, lengthB, (lengthA+lengthB)/2); 7             double r2 = find(A, 0, lengthA, B, 0, lengthB, (lengthA+lengthB)/2+1); 8             return (r1 + r2)/2; 9         }10         else {11             return find(A, 0, lengthA, B, 0, lengthB, (lengthA+lengthB)/2+1);12         }13     }14     15     public double find(int[] A, int a1, int a2, int[] B, int b1, int b2, int k) {16         int lenA = a2 - a1;17         int lenB = b2 - b1;18         if (lenA == 0) return B[b1+k-1];19         if (lenB == 0) return A[a1+k-1];20         if (k == 1) return A[a1]<B[b1]? A[a1]:B[b1];21         int midA = (a1 + a2)/2;22         int midB = (b1 + b2)/2;23         if (A[midA] < B[midB]) {24             if (k <= lenA/2 + lenB/2 + 1) {25                 return find(A, a1, a2, B, b1, midB, k);26             }27             else {28                 return find(A, midA+1, a2, B, b1, b2, k-lenA/2-1);29             }30         }31         else {32             if (k <= lenA/2 + lenB/2 + 1) {33                 return find(A, a1, midA, B, b1, b2, k);34             }35             else {36                 return find(A, a1, a2, B, midB+1, b2, k-lenB/2-1);37             }38         }39     }40 }

Leetcode: Median of Two Sorted Arrays