# 4. Median of Two Sorted Arrays

{% embed url="<https://leetcode.com/problems/median-of-two-sorted-arrays/>" %}

题目要求 O(log(m+n)) 但其实直接暴力解法也能submit，不过这样就不是hard题了...&#x20;

`merge sort` 也可以做，但还是要 O(m+n)，也不够。但从 `merge sort` 可以想到：最终排序好的 merged array 中，median 左边有一部分是`nums1(A)`贡献的，一部分是`nums2(B)`贡献的，右边同理。本质上，如果我们知道`A`贡献了多少元素给左边，多少给右边，然后就可以确定 `merged array median`的位置，所以关键问题就变成了在`A`中找到这个左右分割线。

在`sorted array`中找某个满足特定大小关系的位置，很容易就想到 `binary search`，但还有一个关键是，这个位置要符合什么样的条件？

先整体上看，`A, B`中有两个分割位置，这两个位置左边的数字，全体必须都小于右边的数字。也就是`max(leftA, leftB) < min(rightA, rightB)`，因为`A,B`本身都是`sorted`，所以`leftA<rightA`是肯定的，这个关系就可以被简化为：`leftA<rightB, leftB<rightA`

这样的话，这题思路就变成了较短的`A`做`binary search`，找到符合要求的分割位置。

（Median加上二分法，这题的边界 index 处理太太太太太太烦了...）

{% tabs %}
{% tab title="Brute Force" %}

```python
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        ls = nums1+nums2
        ls.sort()
        if len(ls) % 2 == 0:
            res = (ls[len(ls)//2] + ls[len(ls)//2 - 1]) / 2
            return res
        else:
            res = ls[len(ls) // 2]
            return res
```

{% endtab %}

{% tab title="Binary Search" %}

```python
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        if len(A) > len(B): return self.findMedianSortedArrays(nums2, nums1)
        
        lenMerge = len(A) + len(B)
        startA, endA = 0, len(A)
        
        while startA <= endA:
            cutA = (startA + endA) // 2
            cutB = (len(A) + len(B) + 1) // 2 - cutA
            lA = A[cutA - 1] if cutA != 0 else float('-inf')
            lB = B[cutB - 1] if cutB != 0 else float('-inf')
            rA = A[cutA] if cutA != len(A) else float('inf')
            rB = B[cutB] if cutB != len(B) else float('inf')
            if lA > rB: endA = cutA - 1
            elif lB > rA: startA = cutA + 1
            else:
                isEven = lenMerge % 2 == 0
                if isEven:
                    return (max(lA, lB) + min(rA, rB))/2
                else:
                    return max(lA, lB)
```

{% endtab %}
{% endtabs %}

#### reference:

{% embed url="<https://www.youtube.com/watch?v=ScCg9v921ns>" %}
