4. Median of Two Sorted Arrays

最简单的方法是两个数组一个一个往前找找到中间那个数结束。但是时间复杂度是O(m+n)。既然要求复杂度为O(log(m+n))，所以几乎一定是二分查找。而且应该也不用一个挨着一个找。

许多corner case干扰推导：

1. m + n是奇数还是偶数？奇数的话要取第(m+n)/2 + 1个数。偶数的话要取第(m+n)/2个和第(m+n)/2 + 1个数的平均数？解决方法是设置helper函数，题目本质为：取两个数组的第k大的数。所以判断先判断奇偶，偶的话返回两个helper结果的平均数。
2. m和n谁大？应该一直假设m比n大，如果不是的话，helper两个数组反过来。
3. 开始二分法，两边都取第k/2个数（实际编码时候index=[k/2] -1）
   a. 如果m(k/2) < n(k/2)， 那m这边0~k/2都在前k个里面，换言之，中位数（第k个大的数）肯定不在这里面。（为什么？反证法，如果中文数在m的前k/2里面，那m这边最多k/2 - 1个数，n那边第k/2个比m这边第k/2个大，所以肯定也不是中位数，所以也是最多k/2 - 1个数，最后加一块儿k-2个数，少于k个数。
   所以要把m这边的前k/2个都算进去，然后继续找m后一半和n的全部，找第k - k/2 = k/2个数
   b. 如果m(k/2) = n(k/2)，那如果k为奇数，就是这个数后面那个m和n里面比较小的数。如果k为偶数，就是这俩数。
4. 特殊情况
   a. 最后越来越少不够k/2： 所以要取pa = min(k/2, m),另一边 pb = k - pa而不是简单的两边都是k/2
   b. k = 1时上面算法不需要，也是停止点， 否则pa = 0, pb = 1, 数组index = 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 (double)FindKthLargest(nums1, m, nums2, n, (m + n) / 2 + 1);
        }
        return (FindKthLargest(nums1, m, nums2, n, (m + n) / 2) + FindKthLargest(nums1, m, nums2, n, (m + n) / 2 + 1)) / 2;
    }
    public double FindKthLargest(int[] a, int m, int[] b, int n, int k){
        if(m > n){
            return FindKthLargest(b, n, a, m, k);
        }
        if(m == 0){
            return b[k - 1];
        }
        if(k == 1){
            return Math.Min(a[0], b[0]);
        }
        //Divide k into two parts
        int pa = Math.Min(m, k / 2);
        int pb = k - pa;
        if(a[pa - 1] < b[pb - 1]){
            int[] subArray = new int[m - pa];
            Array.Copy(a, pa, subArray, 0, m- pa);
            return FindKthLargest(subArray, m - pa, b, n, k - pa);
        }
        else if (a[pa - 1] > b[pb - 1]){
            int[] subArray = new int[n - pb];
            Array.Copy(b, pb, subArray, 0, n - pb);
            return FindKthLargest(a, m , subArray, n - pb, k - pb);
        }
        return a[pa - 1];
    }
}