[LeetCode] 4. Median of Two Sorted Arrays

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

Solution 1: 
Implement find the kth smallest, then find the median based on that.

Note when n is even, the subroutine findKth were called twice. It can be optimized by a function that returns both kth and k+1th. Small revision at lines that returns without recursive calls will do.

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int n = len1 + len2;
        // n == 4
        if( 0 == n % 2){
            return (findKth(nums1, nums2, 0, 0, n/2) + findKth(nums1, nums2, 0, 0, n/2 + 1) ) / 2.0;
        }
        // n == 5
        if( 1 == n % 2){
            return findKth(nums1, nums2, 0, 0, n/2+1);
        }
        
        return 0.0;
    }
    
    public int findKth(int[] nums1, int[] nums2, int index1, int index2, int k){
    
        // if k == 4
        // if k == 5

        int len1 = nums1.length - index1;
        int len2 = nums2.length - index2;
        
        if(len1 + len2 < k){
            return Integer.MIN_VALUE;
        }
        
        if(0 == len1)
            return nums2[index2 + k - 1];
        
        if(0 == len2)
            return nums1[index1 + k - 1];
        
        if(1 == k){
            return Math.min(nums1[index1], nums2[index2]);
        }
        
        // error code
        //if(2 == k)
        //   return Math.max(nums1[index1], nums2[index2]);

        // { 0 1 }

        // { 2 3 }

        // compare 0 and 2 is not correct, answer is 1
        
        // if 2 == k, kd2 = 1; 3 == k, kd2 = 1;
        
        int kd2 = k/2;
        if(len1 < kd2){
            return findKth(nums1, nums2, index1, index2 + kd2, k-kd2);
        }
        if(len2 < kd2){
            return findKth(nums1, nums2, index1 + kd2, index2, k-kd2);
        }
        
        int m1 = nums1[index1 + kd2 -1];
        int m2 = nums2[index2 + kd2 -1];
        
        // k = 4 kd2 = 2
        // k = 5 kd2 = 2
        if(m1 == m2){
            if(0 == k % 2)
                return m1;
            else
                {
                    return findKth(nums1, nums2, index1, index2 + kd2, k-kd2);
                }
        }
        
        if(m1 < m2)
            return findKth(nums1, nums2, index1 + kd2, index2, k-kd2);
        
        if(m1 > m2)
            return findKth(nums1, nums2, index1, index2 + kd2, k-kd2);
        
        return Integer.MIN_VALUE;
    }
    
    
}