[English ver]

# 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)).

## Approach 1:

by the way ,this method often failed , maybe is the complexity is too big.

Analysis
This method is easy,first we figure out how to get the median value and how many number we need for calculate median value when the sum of the two arrays size is odd-lengthed or even-lengthed. And then we put the two arrays together sorted from small to large , and then use the method we got to calculate the median value.

Time complexity: O(m+n)
Space complexity:O(m+n)

we can have a optmization of this approach,like that

Analysis

The optmization is we get the index of the median value , when we sorted the array to the index , we can calculate the median value and we don’t need to sorted all the number.

## Approach 2

Analysis

this method is a little hard to understand,many implementations consider odd-lengthed and even-lengthed arrays as two different cases and treat them separately. In fact , this is a little twist.
First, we can define ‘MEDIAN’ i:

“if we cut the sorted array to two halves of equal length, then median is the average of the max number of the small half and min of larger half , is the number near to the cut .

For example, for [ 1 2 ], we make the cut between 1 and 2:
[1 | 2]
the median = (1+2)/2.0 = 1.5 .
The same to the two arrays , we only need to make sure numbers in the right side of the cut of the two arrays bigger than the left side of the cut ,and the size of the left is equal to the size of the right .
I’ll use ‘|’ to represent a cut, and (number | number) to represent a cut made through a number in this article.

for example , [1 2 3],the cut is like [1 (2|2) 3].the median = (2+2)/2.0 = 2.

now we use ‘L’ to represent the number in the left of the cut ,’R’ to represent the number in the right.

we can found that

N Index of L / R
1 0 / 0
2 0 / 1
3 1 / 1
4 1 / 2
5 2 / 2
6 2 / 3
7 3 / 3
8 3 / 4

It is not hard to conclude that index of L = (N-1)/2, and R = N/2. the median = (L + R)/2 = (A[(N-1)/2] + A[N/2])/2

To get ready for the two array situation,we add a few empty number (represented as ‘#’) in between numbers. and use ‘positions’ to represented the position of that .

[1 2] -> [# 1 # 2 #] (N=2)
position 0 1 2 3 4 (N_Position = 5)

[3 4] -> [# 3 # 4 #] (N=2)
position 0 1 2 3 4 (N_Position = 5)

there are always 2*N+1 ‘positions’ of which array length is N. Therefore, the middle cut should be made on the Nth position (0-based). index(L) = (CutPosition-1)/2, index(R) = (CutPosition)/2.

notice that, when we cut the two arrays there are 2N1+2N2+2 positions,so,each side of the cut should be N1+N2 positions, the two position lefted is the cut . so when A2’s cut is at C2 = K , than A1’s cut should be C1 = N1 + N2 -K,for example ,C2 = 2, 那么 C1 = 2 + 2 - C2 = 2.

[# 1 | 2 #]
[# 3 | 4 #]

now we have two L and two R.

L1 = A1[(C1-1)/2]; R1 = A1[C1/2];
L2 = A2[(C2-1)/2]; R2 = A2[C2/2];

L1 = A1[(2-1)/2] = A1[0] = 1; R1 = A1[2/2] = A1[1] = 2;
L2 = A2[(2-1)/2] = A2[0] = 3; R2 = A1[2/2] = A1[1] = 4;

How can we figure out this cut is the cut we want ?
the numbers in left side must be smaller than the numbers in right side .
Because A1 and A2 is sorted , L1 <= R1 && L2 <= R2.so we only need to confirm that L1 <= R2 and L2 <= R1.

Now we can use binary search to find out the result.

If L1 > R1, it means there are too many large numbers on the left half of A1, then we must move C1 to the left at the same time move C2 to the right;
If L2 > R1, then there are too many large numbers on the left half of A2, and we must move C2 to the left , and move C1 to the right .
Otherwise, make it opposite.

After we find the cut, the medium can be computed as (max(L1, L2) + min(R1, R2)) / 2;

1. since C1 and C2 can be mutually determined from each other, we might as well select the shorter array (say A2) and only move C2 around, and calculate C1 accordingly. That way we can achieve a run-time complexity of O(log(min(N1, N2)))
2. The only edge case is when a cut falls on the 0th(first) or the 2Nth(last) position. For instance, if C2 = 2N2, then R2 = A2[2*N2/2] = A2[N2], which exceeds the boundary of the array. To solve this problem, we can imagine that both A1 and A2 actually have two extra elements, INT_MAX at A[-1] and INT_MAX at A[N].

Time complexity ： O(log(min(m,n))) 。m,n is the length of the two arrays.
space complexity ： O(1) .

## Approach 3：

Analysis
this method’s principle is same as the Approach 2.

Time complexity ： O(log(min(m,n))) 。m,n is the length of the two arrays.
space complexity ： O(1) .

## Approach 4:

Analysis
this method is like that, compare the two arrays’s median recursively, and every time ignore a half of the two arrays. if A’s median is smaller than B’s median , then we keep A’s right and B’s left.Otherwise opposite. last ,we will get L and R , use (L+R)/2.0 to get the median.notice that L and R is not index, isn’t start from 0 . when the numbers of the sum of two array’s size is odd-lengthed L is the same as R,Otherwise is different.

Time complexity ： O(log(m + n))
Space complexity ： O(1)

If you have any suggestions to make the logic and implementation more better , or you have some advice on my description. Please let me know!