[LeetCode]4. Median of Two Sorte

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

You may assume nums1 and nums2 cannot be both empty.

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

给出两个有序数组，找出合并后的中位数，给了个限制条件时间在O(log(m + n)),看到log那就肯定是用二分法了。
先扯个远一点的，中位数就是数组中间的那个数，求法和数组长度的奇偶有关，这里介绍个方法可以无视奇偶。核心的原理在于计算机除法的向下取整，6/2=7/2=3。

偶数时：[1,2,3,4,5,6]，midden=(3+4)/2=(arr[2]+arr[3])/2=(arr[n/2-1]+arr[n/2])/2.
n/2-1=(n-2)/2,由于向下取整，4/2=5/2，所以(n-2)/2=(n-1)/2.
于是midden=(arr[(n-1)/2]+arr[n/2])/2；

奇数时:[1,2,3,4,5],midden=3=arr[2]，同样由于向下取整，n=5，n/2=(n-1)/2.
midden=arr[n/2]=arr[(n-1)/2]=(arr[(n-1)/2]+arr[n/2])/2;

综上：无论奇偶，midden=(arr[(n-1)/2]+arr[n/2])/2，记住核心原理，计算机除法的向下取整

回到题目中，我们假设A数组和B数组合二为一（当然不可能在程序中合并，时间限制不允许）
A+B=C,我们假设C是排好序的新数组，现在C可以分为L和R两部分，L中的所有元素R中的
所有元素。L可以分为A1和B1，同样R可以分为A2和B2。因为A1<A2，B1<B2必然成立，因为
A和B是有序数组，所以L<R成立还需要的条件是A1<=B2,B1<=A2。

最后迭代C1和C2来比较，有三种可能
（1）A1>B2说明x需要减小，A1存在过多元素
（2）A2<B1说明x需要增大，A1存在元素过少
（3）A1<=B2,B1<=A2，符合要求，此时midden=（max(A1，B1)+min(A2,B2)）/2
但似乎这只适用于偶数情况下，奇数情况下，例如
[1,3,5,7,9]
[2,4,8,9]并不能得到正确结果，所以还需要我们作进一步处理

下面是这个题解的精髓
A: [1,2,3,4,5]--------->[#,1,#,2,#,3,#,4,#,5,#],长度变为2n+1
B: [1,1,1,1]------------>[#,1,#,1,#,1,#,1,#],长度变为2m+1
借助标记符号#，C总长度为2n+2m+2，这样就变成了偶数个，可以找到一处切割成长度相等的两部分，长度都为m+n+1。在A中C1位置切割，相应的就要在B的C2=m+n-x处切割。
C1=7时，C2=4+5-7=2，切割位置如下
[＃1＃2＃3＃（4/4）＃5＃]
[＃1/1＃1＃1＃]
A1=A2为3，B1=0，B2=1，找出如下关系
A1 = A [（C1-1）/ 2]; A2 = A [C1 / 2];
B1 = B[（C2-1）/ 2]; B2 = B [C2 / 2];
由于允许A1=A2或者B1=B2，人为的把奇偶变成了一种情况

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        if (m < n) return findMedianSortedArrays(nums2, nums1);
        if (n == 0) return (nums1[(m - 1) / 2] + nums1[m / 2]) / 2.0;
        int left = 0, right = 2 * n;
        while (left <= right) {
            int mid2 = (left + right) / 2;
            int mid1 = m + n - mid2;
            double L1 = mid1 == 0 ? Double.MIN_VALUE : nums1[(mid1 - 1) / 2];
            double L2 = mid2 == 0 ? Double.MIN_VALUE : nums2[(mid2 - 1) / 2];
            double R1 = mid1 == m * 2 ? Double.MAX_VALUE : nums1[mid1 / 2];
            double R2 = mid2 == n * 2 ? Double.MAX_VALUE : nums2[mid2 / 2];
            if (L1 > R2) left = mid2 + 1;
            else if (L2 > R1) right = mid2 - 1;
            else return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
        }
        return -1;
    }
}