The Question

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be $O(\log(m+n))$. Constraints: - nums1.length == m - nums2.length == n - 0 <= m <= 1000 - 0 <= n <= 1000 - 1 <= m + n <= 2000 - -10^6 <= nums1[i], nums2[i] <= 10^6

Java

Binary Search

Questions & Insights

Clarifying Questions

What are the constraints on array lengths $m$ and $n$? (e.g., can they both be zero? Usually, at least one is non-empty, and

m+n \geq 1

What is the expected time complexity? (Finding the median in

O(m+n)

is trivial via merging; the gold standard for this problem is

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

Are there constraints on the values within the arrays? (Important for preventing integer overflow when calculating the average of two middle elements).

How should we handle empty arrays? (If one is empty, the median is simply the median of the non-empty array).

Assumptions

The input arrays are sorted in non-decreasing order.

The total number of elements

m+n

is at least 1.

We aim for an

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

time complexity.

We return a double to handle the average of two elements in even-length scenarios.

Thinking Process

Binary Search on Partitions: Instead of merging, we aim to partition both arrays into two halves (Left and Right) such that the total number of elements in the combined left side is equal to (or one more than) the combined right side.

The Partition Property: For a valid partition at index

i

n nums1 and

j

in nums2, we must ensure:

nums1[i-1] \leq nums2[j]

nums2[j-1] \leq nums1[i]

Optimizing the Search Space: To minimize the number of iterations and avoid index-out-of-bounds logic, we always perform the binary search on the shorter array. This ensures the derived index

j

in the longer array is always valid.

Handling Boundaries: If a partition falls at the edge of an array (index 0 or

N

), we use

-\infty

for the left side and

+\infty

for the right side to satisfy the comparison logic.

Implementation Breakdown

Problem Set

Functional Requirement: Find the median of two sorted arrays nums1 and nums2.

Time Complexity:

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

Space Complexity:

O(1)

Input: int[] nums1, int[] nums2.

Output: double.

Approach

Algorithm: Binary Search (on the partition point).

Data Structure: None (Primitive array manipulation).

Complexity:

Time:

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

Space:

O(1)

Implementation

Wrap Up

Advanced Topics

Generalization to k-th Element: This logic can be generalized to find the

k

-th smallest element in two sorted arrays. Instead of partitioning exactly in the middle, we partition such that the left side has

k

elements.

Handling Large Scale Data: If the arrays are too large to fit in memory and are stored on disk or in a distributed system, we can still use a similar binary search approach by requesting specific indices from the storage nodes, resulting in

O(\log N)

network calls rather than

O(N)

data transfer.

Numerical Stability: When calculating (m + n + 1) / 2, if

m

and

n

are extremely large (e.g., close to Integer.MAX_VALUE), one should use m + (n - m + 1) / 2 or use long to prevent overflow, although array sizes in Java are limited by int capacity anyway.