noodleProblems/
Median of Two Sorted Arrays
#04

Median of Two Sorted Arrays

AlgorithmhardArrayBinary SearchDivide And Conquer

Given two arrays nums1 and nums2, each sorted in non-decreasing order, return the median of the combined collection of all their elements.

The median is the middle value once every element from both arrays is merged into one sorted sequence. When the total number of elements is odd, it is the single middle value; when it is even, it is the average of the two middle values. The result is a floating-point number.

Example cases

  • odd total
    in nums1 = [1,3], nums2 = [2]
    out 2
    Merged: [1, 2, 3]. The middle value is 2.
  • even total
    in nums1 = [1,2], nums2 = [3,4]
    out 2.5
    Merged: [1, 2, 3, 4]. The two middle values are 2 and 3, averaged to 2.5.
  • one array empty
    in nums1 = [], nums2 = [1,2,3,4]
    out 2.5
    Merged: [1, 2, 3, 4]. The average of 2 and 3 is 2.5.
  • single element
    in nums1 = [5], nums2 = []
    out 5
    Only one element, so it is the median.

Constraints

  • 0 <= nums1.length, nums2.length <= 1000
  • 1 <= nums1.length + nums2.length
  • -10^6 <= nums1[i], nums2[i] <= 10^6
  • Both nums1 and nums2 are sorted in non-decreasing order.
Saved
nums1 =
[1,3]
nums2 =
[2]