Median of Two Sorted Arrays

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)).
Solution1:

中位数定义：把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数，则中间那个数据就是这群数据的中位数；如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数。

因此，在计算中位数Median时候，需要根据奇偶分类讨论。

解决此题的方法可以依照：寻找一个unioned sorted array中的第k大（从1开始数）的数。因而等价于寻找并判断两个sorted array中第k/2（从1开始数）大的数。

特殊化到求median，那么对于奇数来说，就是求第(m+n)/2 +1（从1开始数）大的数。

而对于偶数来说，就是求第(m+n)/2大（从1开始数）和第(m+n)/2+ 1大（从1开始数）的数的算术平均值。

所以，我们需要判断A[k/2-1]和B[k/2-1]的大小。

如果A[k/2-1]==B[k/2-1]，那么这个数就是两个数组中第k大的数。

如果A[k/2-1]<B[k/2-1], 那么说明A[0]到A[k/2-1]都不可能是第k大的数，所以需要舍弃这一半，继续从A[k/2]到A[A.length-1]继续找。当然，因为这里舍弃了A[0]到A[k/2-1]这k/2个数，那么第k大也就变成了，第k-k/2个大的数了。

如果 A[k/2-1]>B[k/2-1]，就做之前对称的操作就好

eg.

array a:   |       m1      |
array b:   |                          m2            |
M1和M2分别代表两个array的median.
假如M1比M2大， 那么总array的median肯定在 :  
|---------M1
M2 --------|     之间， 那么M1的后面，和M2的前面 都可以扔掉.
假如M1比M2小， 那么总array的median肯定在 :  
M1————|
|————M2     之间， 那么M1的前面，和M2的后面 都可以扔掉.

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int m = A.length;
        int n = B.length;
        
        int k = m + n;
        
        if(k % 2 != 0)
            return findK(A, 0, m, B, 0, n, k / 2);
        else
            return (findK(A, 0, m, B, 0, n, k / 2) + findK(A, 0, m, B, 0, n, k / 2 - 1)) / 2;
        
    }
    
    public double findK(int[] A, int astart, int aend, int[] B, int bstart, int bend, int k) {
        
        if(astart == aend)
            return B[bstart + k];
        else if(bstart == bend)
            return A[astart + k];
        
        if(k == 0)
            return Math.min(A[astart], B[bstart]);
        
        int akey = Integer.MAX_VALUE;
        int bkey = Integer.MAX_VALUE;
        int ak = (k + 1) / 2;
        int bk = (k + 1) / 2;
        
        if(astart + ak - 1 < A.length)
            akey = A[astart + ak - 1];
        if(bstart + bk - 1 < B.length)
            bkey = B[bstart + bk - 1];
        
        if(akey < bkey)
            return findK(A, astart + ak, aend, B, bstart, bend, k - ak);
        else
            return findK(A, astart, aend, B, bstart + bk, bend, k - bk);
        
    }
}