> For the complete documentation index, see [llms.txt](https://loghead.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://loghead.gitbook.io/algorithm-notes/array-matrix-interval-binary-indexed-tree/median-of-two-sorted-arrays.md).

# Median of two Sorted Arrays

> 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)).
>
> **Example 1:**
>
> ```
> nums1 = [1, 3]
> nums2 = [2]
>
> The median is 2.0
> ```
>
> **Example 2:**
>
> ```
> nums1 = [1, 2]
> nums2 = [3, 4]
>
> The median is (2 + 3)/2 = 2.5
> ```

这题最直接的思路就是按 merge two sorted array 的办法，数出来一半的数字。但是那个时间复杂度是 O(m + n)。题目要求 O(log(m+n))

第一个思路是看了九章来的。先看截图

![](/files/-M5syr74TNBnXmJQ2mxw)做法就是在 A, B 两数组中各取第 k/2 个数，比一下 ，小的那边就把所有那个位置之前的数都淘汰了。corner case 就是如果某个数组中（比如说 A\[]）剩下的数不足 k/2 咋办？直接扔掉另外一边的数(B\[])。因为即使A\[]里面剩下的数都比 B 里的小，因为不足 k/2 个，被扔掉的 B 里面的 k/2 个数肯定不会是总体第 k 位的数。

时间复杂度 O(log(m+n))。程序：

```python
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        length = len(nums1) + len(nums2)
        if length % 2 == 1:
            return self.findKth(nums1, 0, nums2, 0, (length + 1) // 2) * 1.0
        else:
            return (self.findKth(nums1, 0, nums2, 0, length // 2)
                   + self.findKth(nums1, 0, nums2, 0, length // 2 + 1)) / 2.0



    def findKth(self, A, idxA, B, idxB, k):
        if k == 1:
            if idxA >= len(A):
                return B[idxB]
            elif idxB >= len(B):
                return A[idxA]
            else:
                return min(A[idxA], B[idxB])

        offset = k // 2 - 1
        if idxA + offset >= len(A):
            return self.findKth(A, idxA, B, idxB + offset + 1, k - k // 2)
        elif idxB + offset >= len(B):
            return self.findKth(A, idxA + offset + 1, B, idxB, k - k // 2)
        elif A[idxA + offset] < B[idxB + offset]:
            return self.findKth(A, idxA + offset + 1, B, idxB, k - k // 2)
        else:
            return self.findKth(A, idxA, B, idxB + offset + 1, k - k // 2)
```

第二个思路的时间复杂度没有达到要求，但是能 AC，时间复杂度 O(log(range)∗(log(n)+log(m)))

思路就是对值二分。程序如下。但是二分比较tricky，想了一阵才明白，在这样的写法下，为什么 二分出来的数值， 肯定是两数组中的某一个数。只能背下来了。 `while lo < hi ... if count >= k hi = mid else lo = mid + 1`

```python
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        length = len(nums1) + len(nums2)
        if length % 2 == 1:
            return self.findKth(nums1, nums2, (length + 1) // 2) * 1.0
        else:
            return (self.findKth(nums1, nums2, length // 2)
                   + self.findKth(nums1, nums2, length // 2 + 1)) / 2.0



    def findKth(self, A, B, k):
        if not A:
            return B[k - 1]
        elif not B:
            return A[k - 1]

        lo, hi = min(A[0], B[0]), max(A[-1], B[-1])

        while lo < hi:                                 # 死记硬背
            mid = (lo + hi) // 2                       #
            if self.countLessEqual(A, B, mid) >= k:    #
                hi = mid                               #
            else:                                      #
                lo = mid + 1                           #

        return lo

    def countLessEqual(self, A, B, value):    # 算小于等于 value 的元素的个数
        import bisect
        return bisect.bisect(A, value) + bisect.bisect(B, value)
```

第三个方法是最好的，有视频教程：<https://www.youtube.com/watch?v=LPFhl65R7ww>

文字解释：<https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/>

时间复杂度 O( log( min(m,n) ) )

来张截图

![](/files/-M5syr76E2QY5vqTdDfd)

思路就是，短的数组为x，长的数组为y，在x中切一刀，相应的在一种切一刀。然后比较大小看是不是切对了，不对的话二分下一个下刀的位置。

程序

```python
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        import sys
        if len(nums1) == 0 and len(nums2) == 0:
            return 0

        m, n = len(nums1), len(nums2)

        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)

        lo, hi = 0, m

        while lo <= hi:
            cutIdx1 = (lo + hi) // 2
            cutIdx2 = (m + n + 1) // 2 - cutIdx1

            if cutIdx1 == 0:
                maxLeft1 = nums2[cutIdx2 - 1]
            else:
                maxLeft1 = nums1[cutIdx1 - 1]

            maxLeft1 = -sys.maxint - 1 if cutIdx1 == 0 else nums1[cutIdx1 - 1]   # 这几行是为了处理 corner cases
            maxLeft2 = -sys.maxint - 1 if cutIdx2 == 0 else nums2[cutIdx2 - 1]   #
            minRight1 = sys.maxint if cutIdx1 == m else nums1[cutIdx1]           #
            minRight2 = sys.maxint if cutIdx2 == n else nums2[cutIdx2]           #

            if maxLeft1 > minRight2:
                hi = cutIdx1 - 1
            elif maxLeft2 > minRight1:
                lo = cutIdx1 + 1
            else:
                ## maxLeft1 <= minRight2 and maxLeft2 <= minRight1. Found solution
                if (m + n) % 2 == 1:
                    return max(maxLeft1, maxLeft2) * 1.0
                else:
                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2) ) / 2.0

            print lo, hi

        return 0
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://loghead.gitbook.io/algorithm-notes/array-matrix-interval-binary-indexed-tree/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.