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)).
Thoughts:
Find K/2th index from first array, call it i and K/2th index from the second, call it j. Now consider this:
1. If A[i] > B[j], then Kth smallest element will include elements more than K/2 elements from array B and less than K/2 elements from array A. So our area of searching reduces to left part of K/2 index in array A and right part of k/2 index in array B, as shown in figure below.
Again since we have already found j definite smallest elements, we will reduce the search for (k-j)th smallest element in reduced search space.
2. Similarly, if A[i] < B[j], our search space reduces to right part of k/2 index in array A and left of K/2 elements of array B, as shown in figure below. Again since we have already found i definite smallest elements, we will reduce the search for (k-i)th smallest element in reduced search space.
| Find Kth smallest in two sorted arrays |
So what will be the base case:
When K is one, then we return the minimum of A[K-1] and B[K-1] (considering the zero based indexing of array) or if one of the array becomes null then return the other array's Kth smallest element.
Solution 1:
public double findMedianSortedArrays(int A[], int B[]) {
int m = A.length, n = B.length;
if(((m+n)&1) == 1) {//m+n: odd
return findKth(A, 0, m-1, B, 0, n-1, (m+n)/2);
} else {
return (findKth(A,0,m-1,B,0,n-1,(m+n)/2)+findKth(A,0,m-1,B,0,n-1,(m+n)/2-1))/2.0;
}
}
public double findKth(int A[], int aStart, int aEnd, int B[], int bStart, int bEnd, int k) {
int aLen = aEnd - aStart + 1;
int bLen = bEnd - bStart + 1;
if(aLen == 0) return B[bStart+k];
if(bLen == 0) return A[aStart+k];
if(k == 0) return Math.min(A[aStart], B[bStart]);
int aMid = aLen*k/(aLen+bLen);
int bMid = k-aMid-1;
aMid += aStart;
bMid += bStart;
if(A[aMid] > B[bMid]) {
k = k - (bMid - bStart + 1);
aEnd = aMid;
bStart = bMid + 1;
} else {
k = k - (aMid - aStart + 1);
aStart = aMid + 1;
bEnd = bMid;
}
return findKth(A, aStart, aEnd, B, bStart, bEnd, k);
}
Complexity of code to find median of two sorted array with above algorithm is O(log (m+n)).
Soltion 2:
public double findMedianSortedArrays(int A[], int B[]) {
int n = A.length;
int m = B.length;
// the following call is to make sure len(A) <= len(B).
// yes, it calls itself, but at most once, shouldn't be
// consider a recursive solution
if (n > m)
return findMedianSortedArrays(B, A);
// now, do binary search
int k = (n + m - 1) / 2;
int l = 0, r = Math.min(k, n); // r is n, NOT n-1, this is important!!
while (l < r) {
int midA = (l + r) / 2;
int midB = k - midA;
if (A[midA] < B[midB])
l = midA + 1;
else
r = midA;
}
// after binary search, we almost get the median because it must be between
// these 4 numbers: A[l-1], A[l], B[k-l], and B[k-l+1]
// if (n+m) is odd, the median is the larger one between A[l-1] and B[k-l].
// and there are some corner cases we need to take care of.
int a = Math.max(l > 0 ? A[l - 1] : Integer.MIN_VALUE, k - l >= 0 ? B[k - l] : Integer.MIN_VALUE);
if (((n + m) & 1) == 1)
return (double) a;
// if (n+m) is even, the median can be calculated by
// median = (max(A[l-1], B[k-l]) + min(A[l], B[k-l+1]) / 2.0
// also, there are some corner cases to take care of.
int b = Math.min(l < n ? A[l] : Integer.MAX_VALUE, k - l + 1 < m ? B[k - l + 1] : Integer.MAX_VALUE);
return (a + b) / 2.0;
}
Solution 3:
int min(int a, int b) {
return a > b ? b : a;
}
int find_kth(int a[], int b[], int size_a, int size_b, int k){
/* to maintain uniformaty, we will assume that size_a is smaller than size_b
else we will swap array in call :) */
if(size_a > size_b) return find_kth(b, a, size_b, size_a, k);
/* Now case when size of smaller array is 0 i.e there is no elemt in one array*/
if(size_a == 0) return b[k-1]; // due to zero based index
/* case where K ==1 that means we have hit limit */
if(k == 1) return min(a[0], b[0]);
/* Now the divide and conquer part */
int i = min(size_a, k/2) ; // K should be less than the size of array
int j = min(size_b, k/2) ; // K should be less than the size of array
if(a[i-1] > b[j-1])
// Now we need to find only K-j th element
return find_kth(a, b+j, size_a, size_b-j, k-j);
else
return find_kth(a+i, b, size_a-i, size_b, k-i);
return -1;
}
double findMedianSortedArrays(int a[], int size_a, int b[], int size_b) {
int left = (size_a + size_b + 1) >>1;
int right = (size_a + size_b + 2) >>1;
return ( find_kth(a,b, size_a,size_b, left) + find_kth(a,b, size_a,size_b, right) )/2.0;
}
References:
http://www.algorithmsandme.com/2014/12/find-median-of-two-sorted-arrays-of.html
http://www.algorithmsandme.com/2014/12/fins-kth-smallest-element-in-two-sorted.html
https://oj.leetcode.com/discuss/11174/share-my-iterative-solution-with-o-log-min-n-m
.png){kind=link}