[LC4] 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)).

題目要求： 

給定兩個排序過的 array: nums1, nums2，size分別為 m, n，找兩個數列的中位數。Time complexity必須是 O(log(m + n))

思路：

原數列的總個數，會影響中位數的求法。當個數為奇數時，中位數就是數列中的第 n/2 + 1個數，當數列為偶數時，就必須拿最接近中間的兩個數字來平均，也就是 avg(num[n/2] + num[n/2 + 1] )。

另外我們寫一個找出兩數列中第 k個數字的 function來找到我們要的數字。此 function利用divide and conquer 的方式，依序把不可能的 portion給刪除掉。因為nums1 and nums2這兩個數列是排序過的，我們分別在兩個數列中，找第 k/2個數，如果這兩個數相等，就代表在 nums1中有 k/2個數<=這個數，nums2中也是一樣，如此得知，這個數在這兩個數列中，是第 k大，就是我們要的答案。

如果 nums1[k/2] < nums2[k/2]，代表小於 nums1[k/2]那些數都太小了，不可能成為兩個數列中第 k大的數字。換句話說，nums2這個數列，會貢獻 > k/2個數，吃掉nums1會貢獻的數目，他只貢獻 < k/2個數，所以比nums1[k/2]小那些數，都只是當墊被的，不可能成為第 k個，所以可以刪去：

a1 a2 a3 ... nums1[k/2] ... nums2[k/2] ...  (第 k大的數，不可能由 < nums1[k/2]那些數字所貢獻)

 反之，如果 nums2[k/2] < nums1[k/2]，代表小於 nums2[k/2]那些數都太小了，不可能成為兩個數列中第 k大的數字：

a1 a2 a3 ... nums2[k/2] ... nums1[k/2] ...  (第 k大的數，不可能由 < nums2[k/2]那些數字所貢獻) 

為了更有效率，我們一開始就 ensure size of nums1 < size of nums2，如此一來，nums1會比較早切完，當他被切完時，就直接找 nums2的第 k個數，就是答案。當然我們這邊保證 k一定小於 (m + n) 

實作：

Time complexity is O(log(m + n))