4. Median of Two Sorted Arrays

Hard

---

Solution

Define separators mid1 and mid2 such that

• nums1 is divided into two parts at mid1.
  • nums1[0:mid1] is the left minimal part. Let's call it mins1.
  • nums1[mid1:m] is the right maximal part. Let's call it maxs1.
• nums2 is divided into two parts at mid2.
  • nums2[0:mid2] is the left minimal part. Let's call it mins2.
  • nums2[mid2:n] is the right maximal part. Let's call it maxs2.
• mins1 & mins2 and maxs1 & maxs2 are the left and right parts of the merged array, respectively.
  • mins1 & mins2 and maxs1 & maxs2 should have the same length or differ by 1.
  • Every elements in mins1 & mins2 are smaller than every elements in maxs1 & maxs2.

Now, initially assign mid1 as the middle index of nums1. mid2 is derived by mid2 = (m + n + 1) // 2 - mid1, by the size constraint of mins1 & mins2 and maxs1 & maxs2.

Then, we can check if mins1 & mins2 and maxs1 & maxs2 are valid by

• Given that the candidates of the maximum of mins1 & mins2 is nums1[mid1 - 1] and nums2[mid2 - 1].
• Given that the candidates of the minimum of maxs1 & maxs2 is nums1[mid1] and nums2[mid2].
• Both nums1[mid1 - 1] and nums2[mid2 - 1] should be smaller than or equal to nums1[mid1] and nums2[mid2].

Note that always nums1[mid1 - 1] <= nums1[mid1] and nums2[mid2 - 1] <= nums2[mid2]. Now, we want to find mid1 and mid2 that satisfies the above conditions, using binary search.

• If the above conditions are satisfied, that is nums1[mid1 - 1] <= nums2[mid2] and nums2[mid2 - 1] <= nums1[mid1], then we found the valid mid1 and mid2.
• If nums1[mid1 - 1] > nums2[mid2], then shorten mins1.
• If nums2[mid2 - 1] > nums1[mid1], then shorten mins2.

Finally, the median is min(maxs1 & maxs2) or (max(mins1 & mins2) + min(maxs1 & maxs2)) / 2. Note that max(mins1 & mins2) = max(nums1[mid1 - 1], nums2[mid2 - 1]) and min(maxs1 & maxs2) = min(nums1[mid1], nums2[mid2]).

---

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

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

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

 

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106