# 4-Median of Two Sorted Arrays
###### tags: `Hard`
>question : https://leetcode.com/problems/median-of-two-sorted-arrays/

>reference :
https://www.javatpoint.com/cpp-program-to-merge-two-unsorted-arrays

>related problem :
## Solution
- 思路:
1. Merge sort可以讓時間複雜度到O(m+n)，即nums1和nums2都逐一比較，較小者放入新陣列中，最後比對完再取中位數
2. 但題目要求O(log(m+n))，所以使用Binary search，將兩個陣列都從中間開始尋找中位數，再依照L1<R2和L2<R1的規則進行修正。nums1和nums2合併且排序的新陣列之中位數前，必定包含分別某些數量來自nums1和nums2，而兩者總和固定，故知道多少來自nums1?即可推得多少來自nums2，各自的中位數也能求得。 *通常nums1是取長度較短的那個陣列，這樣運算之時間複雜度才能較低

3. 看到sorted array就要想到可以使用binary search，或相關的方法。

### ***Merge sort***

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> merged;
        int i = 0, j = 0;
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] < nums2[j]) {
                merged.push_back(nums1[i]);
                i++;
            } else {
                merged.push_back(nums2[j]);
                j++;
            }
        }
        while (i < nums1.size()) {
            merged.push_back(nums1[i]);
            i++;
        }
        while (j < nums2.size()) {
            merged.push_back(nums2[j]);
            j++;
        }
        int mid = merged.size() / 2;
        if ((merged.size() % 2) == 0) {
            return float(merged[mid - 1] + merged[mid]) / 2;
        } else {
            return float(merged[mid]);
        }
    }
};

### ***binary search***

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // m n mid=(m+n)/2
        int m=nums1.size(),n=nums2.size();
        if(m>n) return findMedianSortedArrays(nums2,nums1);
        int l=0,r=m,i,j;
        int l1,l2,r1,r2;
        while(l<=r)
        {
            i=l+(r-l)/2;
            j=(m+n+1)/2-i;
            //i>0 && i<m
            l1=i?nums1[i-1]:INT_MIN;
            l2=j?nums2[j-1]:INT_MIN;
            r1=(i!=m)?nums1[i]:INT_MAX;
            r2=(j!=n)?nums2[j]:INT_MAX;
            if(l1<=r2 && l2<=r1)
                break;
            else if(l1>r2 && l2<=r1)
                r=i-1;
            else
                l=i+1;
        }
        if((m+n)&1) return max(l1,l2);
        return ((double)max(l1,l2)+(double)min(r1,r2))/2;
    }
};