Median of Two Sorted Array
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)).
中位数(Wiki):计算有限个数的数据的中位数的方法是：把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数，则中间那个数据就是这群数据的中位数；如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数。
public double findMedianSortedArrays(int A[], int B[]) {
int lengthA = A.length;
int lengthB = B.length;
if ((lengthA + lengthB) % 2 == 0) {
double r1 =(double) findMedianSortedArrays(A, 0, lengthA, B, 0, lengthB, (lengthA + lengthB) / 2);
double r2 =(double) findMedianSortedArrays(A, 0, lengthA, B, 0, lengthB, (lengthA + lengthB)/2+1);
return (r1 + r2) / 2;
} else
return findMedianSortedArrays(A, 0, lengthA, B, 0, lengthB, (lengthA + lengthB + 1) / 2);
}
public int findMedianSortedArrays(int A[], int startA, int endA, int B[], int startB, int endB, int k){
int n = endA - startA;
int m = endB - startB;
if (n <= 0)
return B[startB + k - 1];
if (m <= 0)
return A[startA + k - 1];
if (k == 1)
return A[startA] < B[startB] ? A[startA] : B[startB];
int midA = (startA + endA) / 2;
int midB = (startB + endB) / 2;
if (A[midA] <= B[midB]) {
if (n / 2 + m / 2 + 1 >= k)
return findMedianSortedArrays(A, startA, endA, B, startB, midB, k);
else
return findMedianSortedArrays(A, midA + 1, endA, B, startB, endB, k - n / 2 - 1);
} else {
if (n / 2 + m / 2 + 1 >= k)
return findMedianSortedArrays(A, startA, midA, B, startB, endB, k);
else
return findMedianSortedArrays(A, startA, endA, B, midB + 1, endB, k - m / 2 - 1);
}
}