# 4. Median of Two Sorted Arrays

## 1.問題

* 找出兩list合併後的中位數

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LJ-XYjH6BdhAv8qSTjK%2F-LJ-YsvRWH5HOQgy3lML%2F2018080303.jpg?alt=media\&token=8c815bac-3757-4c77-a4b9-230326ae0aba)

## 2.想法

* O(m + n): 比較兩list的元素並將最小值先放入list中, return list的中位數
* O(Log(m + n)):&#x20;
  * k的初始值為(m + n) / 2, 每次都將k折半, 並比較nums1\[k/2]與nums2\[k/2], 如果nums1\[k/2]較大, 則下次迭代時將不把比nums2\[k/2]小的數字納入比較; 反之亦然
  * 此做法等於每次屑減 (m + n) /2, 再將剩下的(m + n) / 2個數字進行下一次迭代, 等同於使用Binary search

## 3.程式碼

* O(m + n)

```
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int size1 = nums1.size();
        int size2 = nums2.size();
        
        int index1 = 0, index2 = 0;
        vector<int> v;
        while (index1 < size1 && index2 < size2)
        {
            if (nums1[index1] < nums2[index2])
            {
                v.push_back(nums1[index1]);
                index1++;
            }
            else if (nums1[index1] > nums2[index2])
            {
                v.push_back(nums2[index2]);
                index2++;
            }
            else
            {
                v.push_back(nums1[index1]);
                v.push_back(nums2[index2]);
                index1++;
                index2++;
            }
        }
        
        while (index1 < size1)
        {
            v.push_back(nums1[index1]);
            index1++;
        }
        
        while (index2 < size2)
        {
            v.push_back(nums2[index2]);
            index2++;
        }
        
        return ((size1 + size2) % 2 == 0) ? (double)(v[(size1 + size2 - 1)/2] + v[(size1 + size2 - 1)/2 + 1])/2 : v[(size1 + size2)/2];
    }
}
```

* O(Log(m + n))

```
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
		if (total & 0x1)
        {
            return findKth(nums1, 0, nums2, 0, total / 2 + 1);
        }
		else
			return (findKth(nums1, 0, nums2, 0, total / 2)
					+ findKth(nums1, 0, nums2, 0, total / 2 + 1)) / 2;
    }
private:
    double findKth(vector<int>& a, int idx1, vector<int>& b, int idx2, int k)
    {
        int m = a.size() - idx1; 
        int n = b.size() - idx2;
        if (m > n) {
		    return findKth(b, idx2, a, idx1, k);
        }
	    if (m == 0) {
		    return b[k - 1];
        }
	    if (k == 1) {
		    return min(a[idx1], b[idx2]);
        }
    
        //divide k into two parts
	    int pa = min(k / 2, m), pb = k - pa;
        if (a[idx1 + pa - 1] < b[idx2 + pb - 1]) {
            return findKth(a, idx1 + pa, b, idx2, k - pa);
        }
	    else if (a[idx1 + pa - 1] > b[idx2 + pb - 1]) {
            return findKth(a, idx1, b, idx2 + pb, k - pb);
        }
	    else {
		    return a[pa - 1];
        }
    }
};

```

## 4.References

* [https://blog.csdn.net/yutianzuijin/article/details/11499917](https://blog.csdn.net/yutianzuijin/article/details/11499917)
* [https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf](https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf)
