# Leetcode --- 4. Median of Two Sorted Arrays

## 4. Median of Two Sorted Arrays
### Description:
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Follow up: The overall run time complexity should be O(log (m+n)).
:::info
Example 1:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 2:
Input: nums1 = [], nums2 = [1]
Output: 1.00000
:::

### 解法條列
1. 暴力解: 由兩陣列長度得到中位數索引，依序遍尋兩陣列的元素，規則為從此陣列當前元素小於另一陣列的當前元素才可繼續數，若大於的話則換陣列繼續數。
時間複雜度: O(max(m,n)) ， m、n為兩陣列的長度。

2. 利用中位數的特性找出解。
停止條件為nums1[cut1-1] <= nums2[cut2] and nums2[cut-1] <= nums1[cut1]
令start與end為cut1的兩端，初始數值為0與nums1的尾端。
cut1為start與end的中心點，cut2為兩陣列長度和減去cut1。
若不符合停止條件，則更新start或end(start = cut1+1 或是 end = cut1-1)。
直到找到解。

3. leetcode上看到的最佳解。
兩陣列合併後排序。 ( nums1.extend(nums2)、nums1.sort() )
直接用索引值找中位數。

選擇解法為2。

### 解法細節
提前預防因cut所產生的out of index。
較重要的部分有: 陣列的長短、cut2的計算原理、總陣列長度的奇偶。
讀取陣列時是用cut-1與cut，該如何解釋?

### Python Solution

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if(len(nums1) > len(nums2)):
            nums1, nums2 = nums2, nums1
        start, end = 0, len(nums1)
        total_len = len(nums1) + len(nums2)      
        
        while(1):
            cut1 = (start+end) // 2
            cut2 = total_len//2 - cut1
            
            if(cut1 == 0):
                a = -pow(10,6)
            else:
                a = nums1[cut1-1]
                
            if(cut1 == len(nums1)):
                b = pow(10,6)
            else:
                b = nums1[cut1]
            
            if(cut2 == 0):
                c = -pow(10,6)
            else:
                c = nums2[cut2-1]
            
            if(cut2 == len(nums2)):
                d = pow(10,6)
            else:
                d = nums2[cut2]
                
            if(a<=d and c<=b):
                if(total_len%2 == 0):
                    return (max(a,c) + min(b,d)) / 2
                return (min(b,d))
            elif(a>d):
                end = cut1 - 1
            else:
                start = cut1 + 1
        
        

---

if(cut1 == 0):
    a = -pow(10,6)
else:
    a = nums1[cut1-1]
    
if(cut1 == len(nums1)):
    b = pow(10,6)
else:
    b = nums1[cut1]

if(cut2 == 0):
    c = -pow(10,6)
else:
    c = nums2[cut2-1]

if(cut2 == len(nums2)):
    d = pow(10,6)
else:
    d = nums2[cut2]

這段用於避免out of index的情況發生，事先將out of index的情況替換成上下限數值。

---

if(a<=d and c<=b):
    if(total_len%2 == 0):
        return (max(a,c) + min(b,d)) / 2
    return (min(b,d))
elif(a>d):
    end = cut1 - 1
else:
    start = cut1 + 1

此段為本題精華，若符合a<=d and c<=b的條件，則代表現階段的cut可用來找出中位數。
若a<d不成立，則須將cut1左移，等同於將end左移，令為cut1-1。
令一情況是c<b不成立，則要將cut1右移，等同將start右移，令為cut1+1。
(這裡直接使用else，可以少一次條件判斷)

###### tags: `leetcode` `array` `hard`