The Question

Median of Two Sorted Arrays

Given two sorted numerical arrays of potentially different lengths, implement an efficient algorithm to find the median of the combined sorted set without merging them into a new array. The solution should ideally run in logarithmic time relative to the size of the smaller array.

C++

Binary Search

Array

Questions & Insights

Clarifying Questions

What are the maximum possible sizes for the input arrays? (Determines if an

O(n+m)

linear scan is acceptable or if

O(\log(\min(n, m)))

is required).

Can the input arrays be empty? If both are empty, what is the expected return value?

Are the elements guaranteed to be within the range of a standard integer, and should the median be returned as a double?

Are the arrays sorted in non-decreasing order?

Assumptions:

Arrays are sorted in non-decreasing order.

One array might be empty, but not both.

Time complexity must be

O(\log(\min(n, m)))

to satisfy competitive programming standards for this classic problem.

Median is the middle element for odd total length, and the average of the two middle elements for even total length.

Thinking Process

To find the median efficiently, we don't need to merge the arrays. Instead, we perform a binary search to find a partition point in the smaller array such that elements to the left are smaller than elements to the right.

Let the arrays be

A

B

with sizes

n

and

m

. We seek a partition index

i

A

j

B

such that

i + j = (n + m + 1) / 2

The condition for a valid partition is:

A[i-1] \le B[j]

and

B[j-1] \le A[i]

. If

A[i-1] > B[j]

, we must move the partition in

A

to the left; otherwise, move it to the right.

Handle boundary conditions (where

i

j

are 0 or equal to array size) by using

-\infty

for left-side boundaries and

+\infty

for right-side boundaries.

Implementation Breakdown

Problem Set

Functional Requirement: Return the median of two sorted arrays as a double.

Constraint: Time complexity must be

O(\log(\min(n, m)))

Constraint: Space complexity must be

O(1)

(excluding input storage).

Approach

Algorithm: Binary Search on the partition index.

Data Structure: Standard vectors (input).

Complexity:

Time:

O(\log(\min(n, m)))

where

n, m

are sizes of the arrays.

Space:

O(1)