# \[4]\[困难]\[二分]\[双指针] 寻找两个正序数组的中位数

## 题目描述

[4. 寻找两个正序数组的中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/)

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

```
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
```

示例 2：

```
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
```

示例 3：

```
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
```

示例 4：

```
输入：nums1 = [], nums2 = [1]
输出：1.00000
```

示例 5：

```
输入：nums1 = [2], nums2 = []
输出：2.00000
```

提示：

* nums1.length == m
* nums2.length == n
* 0 <= m <= 1000
* 0 <= n <= 1000
* 1 <= m + n <= 2000
* -106 <= nums1\[i], nums2\[i] <= 106

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

## 解题思路

### 遍历

`nums1`, `nums2`两个数组都是排好序的, 因此在确定中位数需要遍历多少个位数之后, 使用双指针遍历两个数组, 找到最中间的一个数或两个数.

[详细通俗的思路分析，多解法](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/)

如果`nums1`和`nums2`的长度分别为`n`和`m`, 则需要遍历`(n + m) // 2 + 1`次. 考虑到奇偶的区别, 在遍历过程中保存中间的两个数字`left`和`right`. `right`记录当前轮次得到的最小值, `left`记录上一轮的最小值. 在输出时根据两个数组总长度的奇偶性选择输出`right`还是`(left + right) / 2`.

每一轮迭代的过程分为以下几步:

* 更新`left`, 将上一步得到的`right`赋值给`left`
* 求出两个数组中, 当前指针对应的最小值, 就是整体的下一个最小值, 赋值给`right`
* 将上一步找到更小值的指针向后移一位

```python
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n, m = len(nums1), len(nums2)
        index_mid, b_min = (n + m) // 2, (n + m) % 2

        left = right = -1
        first = second = 0
        for _ in range(index_mid + 1):
            left = right
            if first == n:
                right = nums2[second]
                second += 1
            elif second == m:
                right = nums1[first]
                first += 1
            elif nums1[first] <= nums2[second]:
                right = nums1[first]
                first += 1
            else:
                right = nums2[second]
                second += 1

        return right if b_min else (left + right) / 2.0
```

算法的时间复杂度为$$O(N + M)$$.

### 二分

[寻找两个有序数组的中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/)

二分方法的时间复杂度为$$O(\log(m+n))$$. 思路是将原始问题转换为寻找第k小的元素. 如果$$m+n$$长度为奇数, 求第$$\lfloor (m+n) / 2 \rfloor + 1$$小的元素; 如果为偶数, 求第$$\lfloor (m+n) / 2 \rfloor$$小的元素以及第$$\lfloor (m+n) / 2 \rfloor + 1$$小的元素的平均值.

```python
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n, m = len(nums1), len(nums2)
        total_length = n + m

        def get_k_th(k):
            first = second = 0  # 指针
            while 1:
                if first == n:
                    return nums2[second + k - 1]
                elif second == m:
                    return nums1[first + k - 1]
                elif k == 1:
                    return min(nums1[first], nums2[second])

                rad = k // 2 - 1
                next_first = min(n - 1, first + rad)
                next_second = min(m - 1, second + rad)

                if nums1[next_first] <= nums2[next_second]:
                    k -= (next_first - first + 1)
                    first = next_first + 1
                else:
                    k -= (next_second - second + 1)
                    second = next_second + 1

        if (n + m) % 2:
            return get_k_th(total_length // 2 + 1)
        else:
            return (get_k_th(total_length // 2) + get_k_th(total_length // 2 + 1)) / 2.0
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/shu-zu/4-xun-zhao-liang-ge-zheng-xu-shu-zu-de-zhong-wei-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.