## 4. 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 = 

The median is 2.0


Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5


b'
\n
\n\n
\n

## Solution

\n
\n

#### Approach #1 Recursive Approach [Accepted]

\n

To solve this problem, we need to understand "What is the use of median". In statistics, the median is used for:

\n
\n

Dividing a set into two equal length subsets, that one subset is always greater than the other.

\n
\n

If we understand the use of median for dividing, we are very close to the answer.

\n

First let\'s cut into two parts at a random position :

\n
          left_A             |        right_A\n    A, A, ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]\n
\n

Since has elements, so there are kinds of cutting ().

\n

And we know:

\n
\n

\n.

\n

Note: when , is empty, and when , is empty.

\n
\n

With the same way, cut into two parts at a random position :

\n
          left_B             |        right_B\n    B, B, ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]\n
\n

Put and into one set, and put and into another set. Let\'s name them and :

\n
          left_part          |        right_part\n    A, A, ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]\n    B, B, ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]\n
\n

If we can ensure:

\n
\n
\n
1. \n\n
2. \n
3. \n\n
4. \n
\n
\n

then we divide all elements in into two parts with equal length, and one part is always greater than the other. Then

\n

\n\n

\n

To ensure these two conditions, we just need to ensure:

\n
\n
\n
1. \n

\n (or: )
\n if , we just need to set: \n

\n
2. \n
3. \n

\n and \n

\n
4. \n
\n
\n

ps.1 For simplicity, I presume are always valid even if , , , or .\nI will talk about how to deal with these edge values at last.

\n

ps.2 Why ? Because I have to make sure is non-negative since and . If , then may be negative, that will lead to wrong result.

\n

So, all we need to do is:

\n
\n

Searching in , to find an object such that:

\n

\n and where \n

\n
\n

And we can do a binary search following steps described below:

\n
\n
1. Set , , then start searching in \n
2. \n
3. Set , \n
4. \n
5. \n

Now we have . And there are only 3 situations that we may encounter:

\n
\n
• \n

\n and \n
\n Means we have found the object , so stop searching.

\n
• \n
• \n

\n\n
\n Means is too small. We must adjust to get .
\n Can we increase ?
\n \xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0Yes. Because when is increased, will be decreased.
\n \xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0So is decreased and is increased, and may
\n \xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0be satisfied.
\n Can we decrease ?
\n \xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0No! Because when is decreased, will be increased.
\n \xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0So is increased and is decreased, and will
\n \xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0be never satisfied.
\n So we must increase . That is, we must adjust the searching range to .
\n So, set , and goto 2.

\n
• \n
• \n

\n:
\n Means is too big. And we must decrease to get .
\n That is, we must adjust the searching range to .
\n So, set , and goto 2.

\n
• \n
\n
6. \n
\n

When the object is found, the median is:

\n
\n

\n when is odd

\n

\n when is even

\n
\n

Now let\'s consider the edges values where may not exist.\nActually this situation is easier than you think.

\n

What we need to do is ensuring that . So, if and are not edges values (means all exist), then we must check both and .\nBut if some of don\'t exist, then we don\'t need to check one (or both) of these two conditions.\nFor example, if , then doesn\'t exist, then we don\'t need to check .\nSo, what we need to do is:

\n
\n

Searching in , to find an object such that:

\n

\n or or and
\n or or where \n

\n
\n

And in a searching loop, we will encounter only three situations:

\n
\n
\n
1. \n or or and
\n or or \n
\n Means is perfect, we can stop searching.
2. \n
3. \n and and \n
\n Means is too small, we must increase it.
4. \n
5. \n and and \n
\n Means is too big, we must decrease it.
6. \n
\n
\n

Thanks to @Quentin.chen for pointing out that: and . Because:

\n
\n

\n\n

\n

\n\n

\n
\n

So in situation 2. and 3. , we don\'t need to check whether and whether .

\n\n\n

Complexity Analysis

\n
\n
• \n

Time complexity: .
\nAt first, the searching range is .\nAnd the length of this searching range will be reduced by half after each loop.\nSo, we only need loops. Since we do constant operations in each loop, so the time complexity is .\nSince , so the time complexity is .

\n
• \n
• \n

Space complexity: .
\nWe only need constant memory to store local variables, so the space complexity is .

\n
• \n
\n
\n

Analysis written by: @MissMary

\n
'