4. Median of Two Sorted Arrays

Tags： BinarySearch

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)).
Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

public class Solution {
    public int findkth(int A[], int startA, int endA, int B[], int startB, int endB, int k){
        if(endA-startA > endB-startB){
            return findkth(B, startB, endB, A, startA, endA, k);
        }
        if(endA <= startA){
            return B[startB + k - 1];
        }       
        if(k == 1){
            return Math.min(A[startA], B[startB]);
        }
        int ia = Math.min(endA - startA, k / 2);
        int ib = k - ia;
        if(A[startA + ia - 1] < B[startB + ib - 1]){
            return findkth(A, startA+ia, endA, B, startB, endB, ib);
        }else if(A[startA + ia - 1] > B[startB + ib - 1]){
            return findkth(A, startA, endA, B, startB+ib, endB, ia);
        }else{
            return A[startA + ia - 1];
        }
    }
    
    public double findMedianSortedArrays(int A[], int B[]) {
        int lenA = A.length;
        int lenB = B.length;
        
        if(((lenA + lenB)&1) == 0){
            return  (findkth(A, 0, lenA, B, 0, lenB, (lenA+lenB)/2) +
                    findkth(A, 0, lenA, B, 0, lenB, (lenA+lenB)/2+1))/2.0;
        }else{
            return  findkth(A, 0, lenA, B, 0, lenB, (lenA+lenB+1)/2);
        }           
    }
}