###### tags: `Leetcode` `hard` `binary search` `python` `Top 100 Liked Questions`

# 4. Median of Two Sorted Arrays

## [題目來源:] https://leetcode.com/problems/median-of-two-sorted-arrays/

## 題目:
Given two sorted arrays nums1 and nums2 of size m and n respectively, return **the median** of the two sorted arrays.

**The overall run time complexity should be O(log (m+n)).**

## 解題想法:
* 要long(m+n): 往二分法去思考
* 因為最終要return找排好的中位數mid
ex: n=[1,3] m=[2] -> mid=2
ex: n=[1,3] m=[2,4] ->mid=(2+3)/2= 2.5
* 技巧!! 對於奇偶數均適用:
找(m+n+1)/2、(m+n+2)/2 取和平均

#### [高手完整解析] #https://github.com/grandyang/leetcode/issues/4

## Python:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        #技巧:對奇偶均適用:找(m+n+1)/2 (m+n+2)/2 取和平均
        m = len(nums1)
        n = len(nums2)
        left = (m + n + 1) // 2
        right = (m + n + 2) // 2
        return float((self.find_k(nums1, 0, nums2, 0, left) + self.find_k(nums1, 0, nums2, 0, right))) / 2
    
    def find_k(self, nums1, i, nums2, j, k): #i為nums1的起始位置  j為nums2的起始位置 
        #找到第k個元素 
        #特殊case
        if i >= len(nums1): #i已超過nums1長度
            return nums2[j + k - 1]
        if j >= len(nums2): #j已超過nums2長度
            return nums1[i + k - 1]
        if k == 1:
            return min(nums1[i], nums2[j])
        
        #對k二分 分別在nums1、nums2中找k/2個元素:
        #目的為要在nums1、nums2中淘汰k/2個較小數字
        if i + k // 2 - 1 < len(nums1):
            midVal1 = nums1[i + k // 2 - 1]
        else:
            #若個數已經太少 不能淘汰 設無限大避免淘汰
            midVal1 = float("inf")
            
        if j + k // 2 - 1 < len(nums2):
            midVal2 = nums2[j + k // 2 - 1]
        else:
            midVal2 = float("inf")
        
        #二分法 比較兩數組第k/2個小的數字minVal1、2
        #若midVal1小 表示要找的數字不在nums1的前k/2個數字
        #可以將其淘汰 遞迴: 將nums1的起始位置向後移動k/2個
        #將k也減去一半
        if midVal1 < midVal2:
            return self.find_k(nums1, i + k // 2, nums2, j, k - k // 2)
        else:
            return self.find_k(nums1, i, nums2, j + k // 2, k - k // 2)
        
result=Solution()
ans=result.findMedianSortedArrays(nums1 = [1,2], nums2 = [3,4])
print(ans)