Problem
4. Median of Two Sorted Arrays
Find the median of two sorted arrays as if these two are merged as one. The expected complexity is O(log(m + n)), where m and n are the sizes of these two sorted array.
Algorithm
Insights
m1 + m2 = k = (n1 + n2 + 1) / 2- Median is from
{A[m1 - 1], B[m2 - 1], A[m1], B[m2]}- If
n1 + n2is even, the final median is(C[k - 1] + C[k]) / 2 - If
n1 + n2is odd, the final median isC[k - 1]
- If
C[k - 1]= max(A[m1 - 1], B[m2 - 1]) // max of left part
C[k] = min(A[m1], B[m2]) // min of right part- Binary search
m1, whereA[m1] < B[m2 - 1]
Code
public double findMedian(int[] nums1, int[] nums2) {
int n1 = nums1.length;
int n2 = nums2.length;
if (n1 > n2) {
return findMedian(nums2, nums1);
}
int k = (n1 + n2 + 1) / 2;
int l = 0;
int r = n1;
int m1, m2;
while (l < r) {
m1 = l + (r - l) / 2;
m2 = k - m1;
if (nums1[m1] < nums2[m2 - 1]) {
l = m1 + 1;
} else {
r = m1;
}
}
m1 = l;
m2 = k - l;
int n1Left = m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1];
int n2Left = m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1];
int leftMax = Math.max(n1Left, n2Left);
if ((n1 + n2) % 2 == 1) {
return leftMax;
}
int n1Right = m1 >= n1 ? Integer.MAX_VALUE : nums1[m1];
int n2Right = m2 >= n2 ? Integer.MAX_VALUE : nums2[m2];
int rightMin = Math.min(n1Right, n2Right);
return (leftMax + rightMin) * 0.5;
}