Median Of Two Sorted Arrays

Question

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

You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0

LeetCodeleetcode.com/problems/median-of-two-sorted-arrays

Solution

/*
@param: int[] nums1, int[] nums2: input two sorted array;
@return: median.
Algorithm: can be expended to find kth smallest element in two sorted array;
in this case, median is k/2;
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    //corner case
    if (nums1.length == 0 && nums2.length == 0) {
        return 0;
    }

    int k = nums1.length + nums2.length;
    if (k % 2 == 0) {
        return (findKthNumber(nums1, 0, nums2, 0, k/2) +
                findKthNumber(nums1, 0, nums2, 0, k/2+1)) / 2.0;
    }
    return findKthNumber(nums1, 0, nums2, 0, k/2+1);
}

//find kth Number not index, index should be k-1;
public int findKthNumber(int[] A, int startOfA,
                         int[] B, int startOfB,
                         int k) {
    if (startOfA >= A.length) {
        return B[startOfB + k-1];
    }
    if (startOfB >= B.length) {
        return A[startOfA + k-1];
    }

    // should consider last case;
    if (k == 1) {
        return Math.min(A[startOfA], B[startOfB]);
    }

    int halfOfA = (startOfA + k/2-1 >= A.length) ? Integer.MAX_VALUE : A[startOfA + k/2-1];
    int halfOfB = (startOfB + k/2-1 >= B.length) ? Integer.MAX_VALUE : B[startOfB + k/2-1];

    // be careful here, start should be index + number(not index),
    // next k should be k - k/2 (not k/2);
    if (halfOfA < halfOfB) {
        return findKthNumber(A, startOfA + k/2, B, startOfB, k - k/2);
    }else {
        return findKthNumber(A, startOfA, B, startOfB + k/2, k - k/2);
    }
}