# Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 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)).

```    public double findMedianSortedArrays(int[] A, int[] B) {
if (A == null || B == null) {
return -1; //or throw error
}
int size = A.length + B.length;
if (size % 2 == 0) {
return (findMedianHelper(A, 0, B, 0, size / 2) + findMedianHelper(A, 0, B, 0, size / 2 + 1)) / 2.0;
} else {
return findMedianHelper(A, 0, B, 0, size / 2 + 1);
}
}

//find kth element from array A and B which starts from aStart and bStart
public double findMedianHelper(int[] A, int aStart, int[] B, int bStart, int k) {
if (aStart >= A.length) {
return B[bStart + k - 1];
}
if (bStart >= B.length) {
return A[aStart + k - 1];
}
if (k == 1) {
return Math.min(A[aStart], B[bStart]);
}

int aPivot = aStart + k / 2 - 1 < A.length ? A[aStart + k / 2 - 1] : Integer.MAX_VALUE;
int bPivot = bStart + k / 2 - 1 < B.length ? B[bStart + k / 2 - 1] : Integer.MAX_VALUE;

if (aPivot < bPivot) {
return findMedianHelper(A, aStart + k / 2, B, bStart, k - k / 2);
} else {
return findMedianHelper(A, aStart, B, bStart + k / 2, k - k / 2);
}
}```

Now we have N machines, on each there is a sorted array, how to scale it to work together and efficiently find Kth element over all.

Solution 1:

N/2 group, each group has two machine. In each group, do only keep kth of two sorted array, then divide into n/4 groups, each group has 2 machine, keep kth of two sorted arrays again.

Time Complexity: O(K*lgN)

Solution 2:

s = (max+min)/2

Share