4. Median of Two Sorted Arrays

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

先假設nums1長度小於nums2，如果不是，就把1和2順序反過來處理。

做binary search時，以長度較短的nums1為基準來做搜尋partition1的位置，然後再計算出partition2的位置。

partition1和partition2分別是num1和num2分個左右兩半的間隔位置，根據中位數的定義，兩個partitions左邊數字的數量和右邊數字的數量要相等(如果2個array長度加起來是偶數)，或者左邊比右邊多1(如果2個array長度相加為奇數)。

maxLeft1為nums1左半最大的數，minRight1為nums1右半最小的數，maxLeft2為nums2左半最大的數，minRight2為nums2右半最小的數。

由於題目已知nums1和nums2為sorted array，所以maxLeft1必然<=minRight1而maxLeft2必然<=minRight2，所以我們要確認的滿足條件就是maxLeft1 <= minRight2而且maxLeft2 <= minRight1。

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { // time: O(log(m + n)); space: O(1)
    int m = nums1.size(), n = nums2.size();
    if (m > n) return findMedianSortedArrays(nums2, nums1);
    int left = 0, right = m;
    while (left <= right) {
        int partition1 = left + (right - left) / 2;
        int partition2 = (m + n + 1) / 2 - partition1;
        int maxLeft1 = partition1 == 0 ? INT_MIN : nums1[partition1 - 1];
        int minRight1 = partition1 == m ? INT_MAX : nums1[partition1];
        int maxLeft2 = partition2 == 0 ? INT_MIN : nums2[partition2 - 1];
        int minRight2 = partition2 == n ? INT_MAX : nums2[partition2];
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((m + n) % 2 == 0) return (double)(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
            else return (double)(max(maxLeft1, maxLeft2));
        } else if (maxLeft1 > minRight2) {
            right = partition1 - 1;
        } else { // maxLeft1 < minRight2
            left = partition1 + 1;
        }
    }
    return -1.0;
}