The Question

Median of Two Sorted Arrays

Given two separate sorted collections of numerical data, design a highly efficient algorithm to compute the median value of the combined dataset. Your solution should achieve logarithmic time complexity relative to the size of the smaller collection, avoiding a full merge of the data.

Java

Binary Search

Array

Questions & Insights

Clarifying Questions

What is the range of integers and the maximum size of the arrays? Understanding this helps determine if we need to account for integer overflow when calculating indices or the median value (though Java int is usually sufficient for array indices, the median itself might require double).

Are there any memory constraints? Specifically, should the solution be

O(1)

in terms of auxiliary space, or is

O(m+n)

acceptable (the latter being less optimal)?

How should empty arrays be handled? If both are empty, is the behavior defined? If one is empty, should the median of the other be returned?

Are the input arrays guaranteed to be sorted? If not, the complexity would change significantly.

Assumptions:

The input arrays nums1 and nums2 are sorted in non-decreasing order.

Time complexity must be

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

to satisfy competitive programming standards for this specific problem.

Total number of elements

m+n \ge 1

If the total length is even, the median is the average of the two middle elements.

Thinking Process

Binary Search on Partitioning: Instead of merging arrays (which is

O(m+n)

), we aim to find a partition point in both arrays such that the left half and right half of the combined set contain the same number of elements.

Symmetry and the Smaller Array: To minimize the search space, always perform the binary search on the smaller array. This ensures the

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

complexity.

Partition Logic: For a partition index in nums1 and j in nums2, the combined left half consists of nums1[0...i-1] and nums2[0...j-1]. We adjust i using binary search until nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i].

Edge Cases via Sentinels: Handle boundary conditions (where the partition is at the very beginning or end of an array) by using

-\infty

and as virtual elements.

Implementation Breakdown

Problem Set

Functional Requirements: Return the median as a double.

Constraints:

nums1.length == m, nums2.length == n.

0 \le m, n \le 1000

1 \le m + n \le 2000

Time Complexity:

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

Space Complexity:

O(1)

Approach

Algorithm: Binary Search on the partition index.

Data Structure: Array.

Complexity:

Time:

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

Space:

O(1)