Problem
Given two sorted arrays of sizes m and n, find the median of the combined array. Run in O(log(m+n)).
Example
Input: nums1 = [1,3], nums2 = [2]
Output: 2.0Solution
Binary search on the smaller array to find the partition that splits the combined arrays at the median.
def find_median_sorted_arrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2
l, r = 0, m
while l <= r:
i = (l + r) // 2
j = half - i
L1 = nums1[i-1] if i > 0 else float('-inf')
R1 = nums1[i] if i < m else float('inf')
L2 = nums2[j-1] if j > 0 else float('-inf')
R2 = nums2[j] if j < n else float('inf')
if L1 <= R2 and L2 <= R1:
if (m + n) % 2: return max(L1, L2)
return (max(L1, L2) + min(R1, R2)) / 2
elif L1 > R2: r = i - 1
else: l = i + 1function findMedianSortedArrays(nums1, nums2) {
if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];
const m = nums1.length, n = nums2.length;
const half = Math.floor((m + n + 1) / 2);
let l = 0, r = m;
while (l <= r) {
const i = Math.floor((l + r) / 2);
const j = half - i;
const L1 = i > 0 ? nums1[i-1] : -Infinity;
const R1 = i < m ? nums1[i] : Infinity;
const L2 = j > 0 ? nums2[j-1] : -Infinity;
const R2 = j < n ? nums2[j] : Infinity;
if (L1 <= R2 && L2 <= R1) {
if ((m + n) % 2) return Math.max(L1, L2);
return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
} else if (L1 > R2) r = i - 1;
else l = i + 1;
}
}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) swap(nums1, nums2);
int m = nums1.size(), n = nums2.size();
int half = (m + n + 1) / 2;
int l = 0, r = m;
while (l <= r) {
int i = (l + r) / 2;
int j = half - i;
int L1 = i > 0 ? nums1[i-1] : INT_MIN;
int R1 = i < m ? nums1[i] : INT_MAX;
int L2 = j > 0 ? nums2[j-1] : INT_MIN;
int R2 = j < n ? nums2[j] : INT_MAX;
if (L1 <= R2 && L2 <= R1) {
if ((m + n) % 2) return max(L1, L2);
return (max(L1, L2) + min(R1, R2)) / 2.0;
} else if (L1 > R2) r = i - 1;
else l = i + 1;
}
return 0;
}public double findMedianSortedArrays(int[] a, int[] b) {
if (a.length > b.length) { int[] t = a; a = b; b = t; }
int m = a.length, n = b.length, half = (m + n + 1) / 2;
int l = 0, r = m;
while (l <= r) {
int i = (l + r) / 2, j = half - i;
int L1 = i > 0 ? a[i-1] : Integer.MIN_VALUE;
int R1 = i < m ? a[i] : Integer.MAX_VALUE;
int L2 = j > 0 ? b[j-1] : Integer.MIN_VALUE;
int R2 = j < n ? b[j] : Integer.MAX_VALUE;
if (L1 <= R2 && L2 <= R1) {
if ((m + n) % 2 == 1) return Math.max(L1, L2);
return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
} else if (L1 > R2) r = i - 1;
else l = i + 1;
}
return 0;
}Complexity
- Time: O(log(min(m, n)))
- Space: O(1)
Explanation
Partition both arrays so that everything left of the partition contains exactly (m+n+1)/2 elements. Adjust the partition until elements on each side satisfy left ≤ right.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?