LeetCode 4. Median of Two Sorted Arrays

Problem:

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:

Copied from here. I’m such an idiot.

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        if ( total % 2 == 1 ){ //median in the middle number of two arrays
            return (double) findKth( nums1, 0, nums1.length-1, nums2, 0, nums2.length-1,total/2+1 );
        }else{ // median is the average of two middle numbers
            int part1 =  findKth( nums1,0,nums1.length-1,nums2,0,nums2.length-1, total/2);
            int part2 =  findKth( nums1,0,nums1.length-1,nums2,0,nums2.length-1,total/2 + 1);
            return (double) (part1+part2)/2;
        }
    }

    /****
     * Helper function to find the kth element of sub-ranges of two arrays
     */
    private int findKth ( int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k ){
        if (start1 > end1) { //no elements in first array
            return nums2[start2 + k - 1];
        } else if (start2 > end2) { // no elements in second array
            return nums1[start1 + k - 1];
        } else if (k == 1) { // result must be at the head of arrays
            return nums1[start1] < nums2[start2] ? nums1[start1] : nums2[start2];
        } else if (((end1 - start1 + 1) + (end2 - start2 + 1)) == k) { // result in the tails of arrays
            return nums1[end1] > nums2[end2] ? nums1[end1] : nums2[end2];
        }

        // Idetnify the parts of array can be possibly cuts
        int cut1 = (end1 - start1 + 1) < k / 2 ? (end1 - start1 + 1) : k / 2;
        int cut2 = (end2 - start2 + 1) < k / 2 ? (end2 - start2 + 1) : k / 2;

        if (nums1[start1 + cut1 - 1] == nums2[start2 + cut2 - 1] && k == (cut1 + cut2)) {
            //result is the cutting element
            return nums1[start1 + cut1 - 1];
        } else if (nums1[start1 + cut1 - 1] == nums2[start2 + cut2 - 1] && (k + 1) == cut1 + cut2) {
            //reust is the next of cutting element
            int next1 = (start1 + cut1) < nums1.length ? nums1[start1 + cut1] : Integer.MAX_VALUE;
            int next2 = (start2 + cut2) < nums2.length ? nums2[start2 + cut2] : Integer.MAX_VALUE;
            return next1 <= next2 ? next1 : next2;
        } else if (nums1[start1 + cut1 - 1] <= nums2[start2 + cut2 - 1]) {
            //cut first part of the first array
            return findKth(nums1, start1 + cut1, end1, nums2, start2, (cut1 + cut2) >= k ? (start2 + cut2 - 1) : end2, k - cut1);
        } else { //if ( nums1[start1+cut1-1] > nums2[start2+cut2-1]){
            //cut first part of the second array
            return findKth(nums1, start1, (cut1 + cut2) >= k ? (start1 + cut1 - 1) : end1, nums2, start2 + cut2, end2, k - cut2);
        }
    }
}