# 【LeetCode】 4. Median of Two Sorted Arrays

## Description
> 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.

> 有兩個已經排序好的陣列num1和num2，且大小分別是m和n。
> 請找出這兩個陣列合併後的中位數，時間複雜度應為O(log(m+n))。
> 你可以假設陣列不會是空的。

## Example:

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

## Solution

* `num1[i]`和`num2[j]`比較，比較小的那個數，最大情況只可能是第`i+j-1`大。(可能要思考一下)
* 因此我們要找第`k`個數字，我們讓`i`和`j`不超過`k/2`，每次刪去`i`或`j`的可能，讓`k`不斷變小，直到`k=1`，得到答案。
* 建議可以拿測資，照著下方程式碼畫圖跑一次，幫助理解。
* 轉換為指標可以更快。

### Code

class Solution {
public:
    int min(int a,int b)
    {
        return a<b?a:b;
    }
    
    int getkth(int *arr_s,int size_s,int *arr_l,int size_l,int k)
    {
        if(size_s>size_l)
        {
            return getkth(arr_l,size_l,arr_s,size_s,k);
        }
        if(size_s==0)
        {
            return arr_l[k-1];
        }
        if(k==1)
        {
            return min(arr_s[0],arr_l[0]);
        }
        int i=min(size_s,k/2);
        int j=min(size_l,k/2);
        if(arr_s[i-1]>arr_l[j-1])
        {
            return getkth(arr_s,size_s,arr_l+j,size_l-j,k-j);
        }
        else
        {
            return getkth(arr_s+i,size_s-i,arr_l,size_l,k-i);
        }
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int* a = nums1.data();
        int* b = nums2.data();
        int size_a=nums1.size();
        int size_b=nums2.size();
        int l = (size_a + size_b+1) /2.0;
        int r = (size_a + size_b+2) /2.0;
        
        return (getkth(a,size_a ,b,size_b, l) + getkth(a,size_a, b,size_b, r)) / 2.0;
    }
};

###### tags: `LeetCode` `C++`