Description
Return the median of two nondecreasing integer arrays whose combined length is positive. Aim for logarithmic time rather than merging all elements.
Solution
def find_median_sorted_arrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
left, right = 0, m
while left <= right:
i = (left + right) // 2
j = (m + n + 1) // 2 - i
a = nums1[i - 1] if i else float("-inf")
b = nums1[i] if i < m else float("inf")
c = nums2[j - 1] if j else float("-inf")
d = nums2[j] if j < n else float("inf")
if a <= d and c <= b:
return max(a, c) if (m + n) % 2 else (max(a, c) + min(b, d)) / 2
if a > d:
right = i - 1
else:
left = i + 1Examples
Example 1
- Input
[[1,3],[2]]- Output
2
The merged sequence is 1, 2, 3.
Example 2
- Input
[[1,2],[3,4]]- Output
2.5
Average the two middle values.
Example 3
- Input
[[],[7]]- Output
7
Only the second array contributes.
Approach
Binary-search a partition in the shorter array. Choose the other partition so the left half has half the combined elements, rounded up. When both left boundary values are no larger than the opposite right values, use the middle boundary values to compute the median.
Time & space
O(log(min(m,n) + 1)) time and O(1) auxiliary space, where m and n are the two array lengths.