# Median of Two Sorted Arrays

<https://leetcode.com/problems/median-of-two-sorted-arrays/description/>

> 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)).

## Thoughts

<https://www.youtube.com/watch?v=KB9IcSCDQ9k>

让nums1为长度更短的数组, 它们俩长度分别为n1和n2. 找整个排好序的中位数即整个排好序的第k = (n1 + n2 + 1) / 2个.\
k个中有nums1中的m1个(index到m1 - 1)和num2中的m2 = k - m1个(index到m2 - 1).\
为了找出m1和m2是多少, 不难想到可以用两个指针分别指向num1和num2的0位置, 当nums1\[m1]小时m1++, 否则m2++.\
这么做的时间复杂度是O((n1 + n2) / 2).\
我们可以对此过程继续优化.

m1表示把nums1和nums2合并排序后从头到median中nums1的个数, m2 = k - m1 为nums2元素的个数. 对于一共m1 + m2 = k个，如果m1取少了，m2取多了，把在num2中比整个中位数还大的也放进去了，此时一定满足nums1\[m1] < nums\[m2]。因此利用二分法, 当nums\[m1] < nums\[m2]时, 如果再往左移动则前k个会把比nums\[m2]更大的加进去，所以m1只能继续往右边移动。反之同理。\
m1和m2一直代表个数, 二分结束时m1和m2分别指向候选中位元素的下一个。 当k为奇数时, 需要从m1左和m2左中挑一个返回, 由于它们都在k里, 最后一个一定是它们中较大的那个。当k为偶数时, 还要把m1和m2中多选一个然后和k - 1中最大的相加 / 2。

![](/files/-LcOoutMEoZ71CuBpe-L)

## Code

```
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const auto N1 = nums1.size(), N2 = nums2.size();
        // 长的作nums2, 因为后面找nums2中元素时要-1，会出现负数。
        if (N1 > N2) return findMedianSortedArrays(nums2, nums1); 
        int k = (N1 + N2 + 1) / 2, start = 0, end = N1;
        // m1和m2是个数。
        while (start < end) {
            int m1 = start + (end - start) / 2, m2 = k - m1;
            if (nums1[m1] < nums2[m2 - 1]) {
                start = m1 + 1;  
            } else {
                end = m1;
            }
        }
        // 因为是个数，现在指向的都是候选者下一位
        int m1 = start;
        int m2 = k - m1;
        const double c1 = max(m1 == 0 ? INT_MIN : nums1[m1 - 1], m2 == 0 ? INT_MIN : nums2[m2 - 1]);
        if ((N1 + N2) % 2 == 1) return c1; // 此时中位数是k - 1 = m1 + m2 - 1的位置
        const double c2 = min(m1 == N1 ? INT_MAX : nums1[m1], m2 == N2 ? INT_MAX : nums2[m2]);
        return (c1 + c2) / 2;
    }
};
```

## Analysis

时间复杂度O(min(lgn1, lgn2)).


---

# 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://hao-fu-1.gitbook.io/oj/binarysearch/median-of-two-sorted-arrays.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.