> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/6.array/65median-of-two-sorted-arrays.md).

# 65.Median of two Sorted Arrays

## 1.Description(Hard)

There are two sorted arrays\_A\_and\_B\_of size\_m\_and\_n\_respectively. Find the**median**of the two sorted arrays.

**Example**

Given`A=[1,2,3,4,5,6]`and`B=[2,3,4,5]`, the median is`3.5`.

Given`A=[1,2,3]`and`B=[4,5]`, the median is`3`.

[**Challenge**](https://www.lintcode.com/en/problem/median-of-two-sorted-arrays/#challenge)

The overall run time complexity should be`O(log (m+n))`.

## 2.Code

根据复杂度推断算法--summary--find kth number

1.先merge再取median ---O(m+n)(linear algorithm)--优化--O(n) binary search(核心:在O(1)时间内把O(n)变成O(n/2))

2.find median--find kth (n+m)/2 从小到大第k个数--logk--log(n+m)/2

<http://bangbingsyb.blogspot.ca/2014/11/leetcode-median-of-two-sorted-arrays.html>

<http://fisherlei.blogspot.ca/2012/12/leetcode-median-of-two-sorted-arrays.html>

<http://m.blog.csdn.net/article/details?id=11499917>

<http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/>

![](/files/-M33gxOU4XVghc4XctXh)

![](/files/-M33gxOWFYFrd4pXni_P)

![](/files/-M33gxOYMv88nIZFmnho)<http://fisherlei.blogspot.ca/2012/12/leetcode-median-of-two-sorted-arrays.html>

O(n)的解法比较直观，直接merge两个数组，然后求中间值。而对于O(log(m+n))显然是用二分搜索了， 相当于“Kth element in 2 sorted array”的变形。如果(m+n)为奇数，那么找到“(m+n)/2+1 th element in 2 sorted array”即可。如果（m+n）为偶数，需要找到(m+n)/2 th 及(m+n)/2+1 th，然后求平均。

而对于“Kth element in 2 sorted array”， 如下图，两个中位数 A\[m/2] 和 B\[n/2]， 可以将数组划分为四个部分。而丢弃哪一个部分取决于两个条件：1， (m/2 + n/2)?k；2，A\[m/2] ? B\[n/2];

[![](http://1.bp.blogspot.com/-hSOpFyNmfVA/UNvAvU8Q2JI/AAAAAAAAG9A/5spZwyy5vwM/s400/Picture3.png)](http://1.bp.blogspot.com/-hSOpFyNmfVA/UNvAvU8Q2JI/AAAAAAAAG9A/5spZwyy5vwM/s1600/Picture3.png)

如果 (m/2 + n/2) > k，那么意味着，当前中位数取高了，正确的中位数要么在 Section 1或者Section3中。如果A\[m/2] >

B\[n/2], 意味着中位数肯定不可能在Section 2里面，那么新的搜索可以丢弃这个区间段了。同理可以推断出余下三种情况，如下所示：

![](/files/-M33gxO_FiJpsJtg1IgZ)

简单的说，就是或者丢弃最大中位数的右区间，或者丢弃最小中位数的左区间。