# 4 Median of Two Sorted Arrays

## 4. [Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/description/)

## 1. Question

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
```

## 2. Implementation

**(1) Binary Search**

思路: 这题要我们求两个有序数组的合并后的中位数，其实就相当于找第k个数，其中k = (m + n)/2, m和n分别为两个数组的长度。我们可以利用二分的思想，缩小搜索的范围。做法是，分别对两个数组nums1和nums2找出各自前k/2个数，假设nums1的第k/2个数的位置是m, nums2的第k/2个数的位置是n， 如果nums1\[m] < nums2\[n], 说明nums1的前m个数肯定小于第k个数，所以抛弃num1的前k/2个数。这里用[反证法证明](http://blog.csdn.net/yutianzuijin/article/details/11499917/). 最后要注意一些边界条件处理

```java
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;

        if (len % 2 == 0) {
            return 0.5 * findKthNumber(nums1, 0, nums2, 0, len/2 + 1) + 0.5 * findKthNumber(nums1, 0, nums2, 0, len/2);
        }
        else {
            return findKthNumber(nums1, 0, nums2, 0, len/2 + 1);
        }
    }

    public int findKthNumber(int[] nums1, int index1, int[] nums2, int index2, int k) {
        if (index1 >= nums1.length) {
            return nums2[index2 + k - 1];
        }

        if (index2 >= nums2.length) {
            return nums1[index1 + k - 1];
        }

        if (k == 1) {
            return Math.min(nums1[index1], nums2[index2]);
        }

        // 减一是因为k指的是k个元素，而数组是从0开始
        int mid = k/2 - 1;

        int mid1 = index1 + mid >= nums1.length ? Integer.MAX_VALUE : nums1[index1 + mid];
        int mid2 = index2 + mid >= nums2.length ? Integer.MAX_VALUE : nums2[index2 + mid];

        if (mid1 < mid2) {
            return findKthNumber(nums1, index1 + k/2, nums2, index2, k - k/2);
        }
        else {
            return findKthNumber(nums1, index1, nums2, index2 + k/2, k - k/2);
        }
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度O(log(m + n)), 空间复杂度O(log(m + n)),因为递归


---

# 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://protegejj.gitbook.io/oj-practices/chapter1/binary-search/4-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.