4. Median of Two Sorted Arrays

6/11/2018 update:
Why use R value instead of L when len is odd?
Because cutR starts  with nums1.length, the mid point drops on right, so that the right part has more numbers.
这道题到道理懂，会实现。但是为什么这样实现还是一头雾水。为什么cutL要从length开始，二分条件是cutL <= cutR?
--------------------------------------------------------------------------------------------------------------------------

01/19/2018
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)).

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

Analysis:

		L1		L2
nums1:	3	5	|	8	9								cut1: 2
nums2:	1	2	7	|	10	11	12						cut2: 3
			R1		R2
nums3:	1	2	3	4	5	7	|	8	9	10	11	12

See the above table. If the cuts reach median, L1, L2, R1 and R2 satisfy the below conditions:

L1 <= R2

R1 <= L2

Then use binary search to tune cut1. 

if ( L1 > R2) cut1 move left.

if ( R1 > L2) cut1 move right.

cut2 = total lenth / 2 - cut1.

这道题朋友facebook onsite面过原题， 他就是用的二分法， 面试官评价很高。

Solution:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int len = nums1.length + nums2.length;
        int cut1 = 0;
        int cut2 = 0;
        int cutL = 0;
        int cutR = nums1.length;

        while (cutL <= cutR) {
            cut1 = cutL + (cutR - cutL) / 2;
            cut2 = len/2 - cut1;

            int L1 = (cut1 == 0) ? Integer.MIN_VALUE : nums1[cut1 - 1];
            int L2 = (cut2 == 0) ? Integer.MIN_VALUE : nums2[cut2 - 1];
            int R1 = (cut1 == nums1.length) ? Integer.MAX_VALUE : nums1[cut1];
            int R2 = (cut2 == nums2.length) ? Integer.MAX_VALUE : nums2[cut2];

            if (L1 > R2) {
                cutR = cut1 - 1;
            } else if (R1 < L2) {
                cutL = cut1 + 1;
            } else {
                if (len % 2 == 0) {
                    L1 = L1 > L2 ? L1 : L2;
                    R1 = R1 < R2 ? R1 : R2;
                    return (L1 + R1) / 2.0;
                } else {
                    return R1 < R2 ? R1 : R2;
                }
            }
        }

        return -1;
    }
}