Median of two Sorted Arrays

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

Thoughts

先把找中点generalize成找第k个元素。findKth使用了二分的思想，只是和传统二分模板不同，我们用递归做。

Code

class Solution {
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        if ((A.length + B.length) % 2 == 0) {
            return (findKth(A, 0, B, 0, (A.length + B.length) / 2) + findKth(A,
                    0, B, 0, (A.length + B.length) / 2 + 1)) / 2.0;
        } else {
            return findKth(A, 0, B, 0, (A.length + B.length) / 2 + 1);
        }
    }

    // 从 以A_start和B_start为开始的两个数组所合并的数组中寻找第k大的数
    public int findKth(int[] A, int A_start, int[] B, int B_start, int k) {
        // base-cases
        if (A_start == A.length) {
            return B[B_start + k - 1];
        } else if (B_start == B.length) {
            return A[A_start + k - 1];
        }

        // 相当于A_start + B_start 代表的长度始终比k大1
        // 当k == 1时, 代表仅剩一个元素待取, 从剩下的两个选项中小的优先级高
        if (k == 1) {
            return Math.min(A[A_start], B[B_start]);
        }

        // induction cases
        int A_key = A_start + k / 2 - 1 < A.length ? A[A_start + k / 2 - 1]
                : Integer.MAX_VALUE; // 引入MAX相当于说A已满, 退出竞争
        int B_key = B_start + k / 2 - 1 < B.length ? B[B_start + k / 2 - 1]
                : Integer.MAX_VALUE;
        if (A_key < B_key) {
            return findKth(A, A_start + k / 2, B, B_start, k - k / 2);
        } else {
            return findKth(A, A_start, B, B_start + k / 2, k - k / 2);
        }
    }

}

Analysis

二分法，时间复杂度为O(lg(m+n))