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

You may assume nums1 and nums2 cannot be both empty.

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

Analyzation:

Median will divide the array into two parts with equal length.

Given len(A) = m, len(B) = n, if we have:

left         |               right

A[0],A[1]...A[i - 1] | A[i], A[i + 1] ... A[m - 1]

B[0],B[1]...B[j - 1] | B[j], B[j + 1] ... B[n - 1]

And

For A and B, len(left) == len(right);
A[i - 1] < B[j] && B[j - 1] < A[i];

We can get median = (max(A[i - 1], B[j - 1]) + max(A[i] + B[j])) / 2;

Ps: Need to keep m <= n since j = (m + n) / 2 - i and 0 < i < m. When m > n, j will be negative.

So our objective is to find

  left   | right
A[i - 1] | A[i]
B[j - 1] | B[j]
maxLeft = max(A[i - 1], B[j - 1]);
minRight = min(A[i], B[j]);