AlgoViz
HomeBinary Search

Median of 2 sorted arrays

Hard

Binary search the split point

Problem

Given two sorted arrays arr1 and arr2 of size m and n respectively, return the median of the two sorted arrays. The median is defined as the middle value of a sorted list of numbers. In case the length of the list is even, the median is the average of the two middle elements.

In simple words

Binary-search a split of the smaller array so left halves hold exactly half the numbers.

The idea

Choose how many elements of the combined left half come from the smaller array; the rest come from the other. Binary search that count until the four boundary values interleave correctly, and the median falls out of them in O(log min(m,n)).

The trick

  • Always binary search the shorter array to keep the bounds valid.
  • The correct split satisfies maxLeftA <= minRightB and maxLeftB <= minRightA.
  • Use infinities for the out-of-range boundary values.
a[1,3]
b[2]

Step 1 of 5. Brute force: merge both sorted arrays, then read off the middle value. a [1,3], b [2].

1/5
Brute force
timeO(m+n)spaceO(m+n)

Merge then pick.

1const merged = [];2while (i < a.length || j < b.length) merged.push(takeSmaller());3return median(merged);

Memory

last
—
a
[1,3]
b
[2]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
a = [1, 3], b = [2]
Output:
2
Explanation:
Merged 1,2,3 → median 2.

Example 2

Input:
a = [1, 2], b = [3, 4]
Output:
2.5
Explanation:
Middle two are 2 and 3 → 2.5.

Example 3

Input:
a = [0, 0], b = [0, 0]
Output:
0.0
Explanation:
All zeros → 0.

Constraints

  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= arr1[i], arr2[i] <= 10^6

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.