All problems

Median of Two Sorted Arrays

Hard · binary search

You are given two lists of integers, nums1 and nums2, each already sorted in ascending order. Imagine pouring all of their values into one sorted list. Return the median of that combined list as a decimal number.

The median is the middle value when the combined list has an odd length. When the length is even, it is the average of the two middle values. Repeated values count once per occurrence.

For example, the combined list [1, 2, 3, 4] has median 2.5, and [5, 7, 9] has median 7.0. One of the two lists may be empty, but not both.

Examples

Example 1

Input: nums1 = [1, 4], nums2 = [2, 3, 9]

Output: 3.0

The combined list is [1, 2, 3, 4, 9]. Its length is odd, so the median is the middle value, 3.

Example 2

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

Output: 2.5

The combined list is [1, 2, 3, 4]. The two middle values are 2 and 3, and their average is 2.5.

Example 3

Input: nums1 = [], nums2 = [6]

Output: 6.0

With a single value, that value is the median.

Constraints

• 0 <= len(nums1) <= 2000
• 0 <= len(nums2) <= 2000
• 1 <= len(nums1) + len(nums2)
• -10^6 <= nums1[i], nums2[i] <= 10^6
• Both lists are sorted in ascending order. Values may repeat.