leetcode4---Median of Two Sorted

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
题目分析：给出两个长度分别为m和n的排好序的数组，求出他们的中位数，要求时间复杂度为O(log (m+n))。此时看到题目要求就知道把两个数组排序合并为一个的时间复杂度显然超了，这里要求的时间复杂度为O(log (m+n))，那么显然联想到了二分查找的方法，且本题要求的是找中位数，那么我们就用二分的思想来解决问题。
我们将问题转换为求两个排序数组中第k小的数的计算。
定义函数findKth，输入参数依次为nums1,nums2,nums1的起止坐标与nums2的起止坐标以及整数k，这里我们要保证m长度是小于n的，如果不是，颠倒一下就可以了。假设我们已经有了这个函数，我们可以先求出两个数组的长度m，n，如果长度之和total为奇数，则返回第total/2+1位置。如果为偶数，则返回第total/2和total/2+1的平均值，结果就是我们所要的。
我们再来看findKth的求法。首先，保证nums1剩下的长度小于nums2剩余长度，如果不是，则颠倒顺序。当m==0，即剩余长度小的那部分没有元素时，直接返回nums的第k-1位置。当k＝＝1时，直接返回两个数组起始位置中最小值。如果都不是，则进行判断。默认情况下，两个数组长度都应该大于k/2,我们比较的是nums1[k/2]与nums2[k/2]。我们先计算小的数组长度与k/2比较，取最小的一个防止溢出，也就是比较nums1[aStart + partA - 1]与nums2[bStart + partB - 1]的大小，如果两个相等，则不用再比了，返回任意一个就是我们需要的答案；如果nums1[aStart + partA - 1]<nums[bStart + partB - 1]则说明partA中的元素都符合要求，此时应该在nums1刨除partA的元素和nums2的元素中查找，同时更新k值为k－partA；nums1[aStart + partA - 1]>nums[bStart + partB - 1]同理，此时更新partB即可，最终得到一个类似于二分的步骤，时间复杂度为O(log (m+n))。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int total = m + n;
        if (total % 2 != 0) {
            return findKth(nums1, 0, m - 1, nums2, 0, n - 1, total / 2 + 1);
        } else {
            double x = findKth(nums1, 0, m - 1, nums2, 0, n - 1, total / 2 );
            double y = findKth(nums1, 0, m - 1, nums2, 0, n - 1, total / 2 + 1);
            return (x + y) / 2;
        }
    }

    private double findKth(int[] nums1, int aStart, int aEnd, int[] nums2, int bStart, int bEnd, int k) {
        int m = aEnd - aStart + 1;
        int n = bEnd - bStart + 1;
        if (m > n)
            return findKth(nums2, bStart, bEnd, nums1, aStart, aEnd, k);
        if (m == 0)
            return nums2[k - 1];
        if (k == 1)
            return Math.min(nums1[aStart], nums2[bStart]);
        int partA = Math.min(k / 2, m);
        int partB = k - partA;
        if (nums1[aStart + partA - 1] < nums2[bStart + partB - 1])
            return findKth(nums1, aStart + partA, aEnd, nums2, bStart, bEnd, k - partA);
        else if (nums1[aStart + partA - 1] > nums2[bStart + partB - 1])
            return findKth(nums1, aStart, aEnd, nums2, bStart + partB, bEnd, k - partB);
        else
            return nums1[aStart + partA - 1];
    }