Median of two sorted arrays

Hard

Problem

Given two sorted arrays of sizes m and n, return the median of all m + n values combined. With an even total, the median is the average of the two middle values. The target is O(log(min(m, n))) time.

Example 1

Input:  a = [1, 3], b = [2]
Output: 2

Example 2

Input:  a = [1, 2], b = [3, 4]
Output: 2.5

Merged [1, 2, 3, 4]: (2 + 3) / 2.

Also asked as: Median of 2 sorted arrays of equal size · Median of 2 sorted arrays of different size

Test cases

Case 1

Input:    [1,3], [2]
Expected: 2

Case 2

Input:    [1,2], [3,4]
Expected: 2.5

Case 3

Input:    [], [1]
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Binary search on the partition of the smaller array

Time O(log min(n, m))Space O(1)

Choose how many of the first array go in the left half; derive the count from the second. Slide until maxLeft ≤ minRight on both sides.

function findMedianSortedArrays(a, b) {
if (a.length > b.length) [a, b] = [b, a];
const n = a.length, m = b.length, half = (n + m + 1) >> 1;
let lo = 0, hi = n;
while (lo <= hi) {
const i = (lo + hi) >> 1; // from a
const j = half - i; // from b
const aLeft = i > 0 ? a[i - 1] : -Infinity;
const aRight = i < n ? a[i] : Infinity;
const bLeft = j > 0 ? b[j - 1] : -Infinity;
const bRight = j < m ? b[j] : Infinity;
if (aLeft <= bRight && bLeft <= aRight) {
if ((n + m) % 2) return Math.max(aLeft, bLeft);
return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;
}
if (aLeft > bRight) hi = i - 1;
else lo = i + 1;
}
throw new Error('inputs not sorted');
}