Median of Two Sorted Arrays

题目地址:
https://leetcode.com/problems/median-of-two-sorted-arrays/#/description

题目：

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

解题思路：
这道题需要用到二分的思想。需要从两个array里面找第(m + n) / 2个数，那么每次将需要找的数减少一半，所以总共的时间复杂度是O((m + n) / 2)。follow up：如果是k个sorted list找medium，那么只能够用minheap来实现，时间复杂度是O(kn * lg(k))。这道题也可以衍生为find kth element in k sorted list。

代码：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    int part1 = (m + n + 1) / 2;
    int part2 = (m + n + 2) / 2;
    return (getKth(nums1, 0, nums2, 0, part1) + getKth(nums1, 0, nums2, 0, part2)) / 2.0;
}
private int getKth(int[] a, int aleft, int[] b, int bleft, int k){
    if(aleft >= a.length){
        return b[bleft + k - 1];
    }
    if(bleft >= b.length){
        return a[aleft + k - 1];
    }
    if(k == 1){
        return Math.min(a[aleft], b[bleft]);
    }
    int amid = aleft + k / 2 - 1;
    int bmid = bleft + k / 2 - 1;
    int aval = amid >= a.length ? Integer.MAX_VALUE : a[amid];
    int bval = bmid >= b.length ? Integer.MAX_VALUE : b[bmid];
    if(aval <= bval){
        return getKth(a, amid + 1, b, bleft, k - k / 2);
    }
    else{
        return getKth(a, aleft, b, bmid + 1, k - k / 2);
    }
}