The problem
Given two sorted arrays nums1 and nums2, return the median of all their numbers together — the middle value, or the average of the two middle values when the total count is even.
It must run in O(log(m + n)) time.
Examples
- Input
nums1 = [1, 3], nums2 = [2]
- Output
2
- Input
nums1 = [1, 2], nums2 = [3, 4]
- Output
2.5
Constraints
- 0 ≤ m, n ≤ 1000, and m + n ≥ 1
- −10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶
The idea
The median splits all the numbers into a left half and a right half with everything on the left ≤ everything on the right. The left half takes some i numbers from the front of one array and half − i from the front of the other; choosing i fixes the split.
A split is right when the largest on the left of each array is ≤ the smallest on the right of the other. If the first array’s left side is too big, take fewer from it; otherwise take more. That is a binary search over i in the shorter array. The median is then read off the four numbers at the cut.
- Time
- O(log min(m, n))
- Space
- O(1)
Solution · every language run against every case
class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: a, b = (nums1, nums2) if len(nums1) <= len(nums2) else (nums2, nums1) # search the shorter m, n = len(a), len(b) half = (m + n + 1) // 2 # how many elements belong on the left lo, hi = 0, m while True: i = (lo + hi) // 2 # take i from a and half - i from b for the left side j = half - i a_left = a[i - 1] if i > 0 else float("-inf") a_right = a[i] if i < m else float("inf") b_left = b[j - 1] if j > 0 else float("-inf") b_right = b[j] if j < n else float("inf") if a_left <= b_right and b_left <= a_right: # everything left <= everything right if (m + n) % 2: return float(max(a_left, b_left)) return (max(a_left, b_left) + min(a_right, b_right)) / 2 if a_left > b_right: hi = i - 1 # took too many from a else: lo = i + 1 # took too few from a