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

Have you been asked this question in an interview? 

Discuss

public class Solution {
    public double findMedianSortedArrays(int a[], int b[]) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int m = a.length;
        int n = b.length;
        int total = m + n;
        if((total)%2==1) {
            return findKth(a, 0, m, b, 0, n, total/2 + 1);
        } else {
            return (findKth(a, 0, m, b, 0, n, total/2) +
                            findKth(a, 0, m, b, 0, n, total/2 + 1))/2.0;
        }
    }

    private double findKth(int a[], int i, int m, int b[], int j, int n, int k) {
        if(m>n) {
            return findKth(b, j, n, a, i, m, k);
        }
        if(m==0)
            return b[j+k-1];
        if(k==1)
            return Math.min(a[i], b[j]);
        int pa = Math.min(k/2, m);
        int pb = k - pa;
        if(a[i+pa-1]>b[j+pb-1]) {
            return findKth(a, i, m, b, j+pb, n-pb, k - pb);
        } else if(a[i+pa-1]<b[j+pb-1]){
            return findKth(a, i+pa, m-pa, b, j, n, k - pa);
        } else {
            return a[i + pa - 1];
        }
    }
}


public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if ((m + n) % 2 == 1) {
            return findKth(nums1, 0, m, nums2, 0, n, (m + n) / 2 + 1);
        } else {
            return (findKth(nums1, 0, m, nums2, 0, n, (m + n) / 2 + 1) + findKth(nums1, 0, m, nums2, 0, n, (m + n) / 2))/2;
        }
    }
   
    public double findKth(int[] nums1, int s1, int l1, int[] nums2, int s2, int l2, int k) {
        if (l1 > l2) {
            return findKth(nums2, s2, l2, nums1, s1, l1, k);
        }
        if (l1 == 0) {
            return nums2[s2 + k -1];
        }
        if (k == 1) {
            return Math.min(nums1[s1], nums2[s2]);
        }
        int p1 = Math.min(l1, k / 2);
        int p2 = k - p1;
        if (nums1[s1 + p1 - 1] > nums2[s2 + p2 - 1]) {
            return findKth(nums1, s1, p1, nums2, s2 + p2, l2 - p2, k - p2);
        } else {
            return findKth(nums1, s1 + p1, l1 - p1, nums2, s2, p2, k - p1);
        }
    }
}