> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/4-median-of-two-sorted-arrays.md).

# 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)),因为递归