Problem

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

Example
Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

Challenge 
The overall run time complexity should be O(log (m+n)).

first idea comes up in my mind

• merge two sorted array, get middle 1 or 2 elements in this array
• O(m + n) time

Optimization

• the lower time complexity would probably be O(log(m + n))
• so, T(m + n) = T(m + n / 2)
• idea of binary search comes up, but not apply to two arrays
• 
  • 函数定义的补充: 从A的某个位置, 和B的某个位置开始, 找第k个数.

    public double findMedianSortedArrays(int[] A, int[] B) {
        int aLen = A.length;
        int bLen = B.length;
        int len = aLen + bLen;

        if (len % 2 == 0) {
            return (findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)) / 2;
        } else {
            return findKth(A, 0, B, 0, len / 2 + 1);
        }
    }

    private double findKth(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 keyA = Integer.MAX_VALUE;
        int keyB = Integer.MAX_VALUE;

        keyA = aStart + k/2 - 1 >= A.length ? keyA : A[aStart + k/2 - 1];
        keyB = bStart + k/2 - 1 >= B.length ? keyB : B[bStart + k/2 - 1];

        if (keyA < keyB) {
            return findKth(A, aStart + k/2, B, bStart, k - k/2);
        } else {
            return findKth(A, aStart, B, bStart + k/2, k - k/2);
        }
    }