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 must be $O(\log (m+n))$. Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2. Example 2: Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. 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

C++

Binary Search

Questions & Insights

Clarifying Questions

What are the constraints on the input array sizes? Are they small enough for an

O(m+n)

approach, or do we strictly need

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

? (Assuming the latter for high performance).

Can the arrays contain duplicate values? (Assuming yes, as it is standard for this problem).

What should be returned if both arrays are empty? (Assuming at least one array is non-empty per standard constraints).

Is the output always a double? (Yes, since the median of an even number of elements is the average of two middle elements).

Assumptions

The arrays are sorted in non-decreasing order.

Time complexity must be logarithmic relative to the size of the arrays.

Space complexity should be

O(1)

(ignoring input storage).

Thinking Process

Partitioning Logic: The goal is to partition both arrays into two halves (Left and Right) such that the total number of elements in the left side equals the total number of elements in the right side (or is one greater).

Binary Search on Indices: Instead of merging, we perform a binary search on the partition point of the smaller array. Let partitionX be the split point in array A. The split point in array B (partitionY) is then uniquely determined by the formula: (m + n + 1) / 2 - partitionX.

Validation Conditions: A partition is valid if:

maxLeftX <= minRightY

maxLeftY <= minRightX

Edge Case Handling: If a partition is at the 0th index or the

N

th index, we use

-\infty

and respectively to ensure the comparison logic remains consistent without bounds errors.

Implementation Breakdown

Problem Set

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

Constraint:

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

time complexity.

Constraint:

O(1)

auxiliary space complexity.

Approach

Algorithm: Binary Search (on partition index).

Data Structure: std::vector<int>.

Complexity:

Time:

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

where

m

and

n

are lengths of the two arrays.

Space:

O(1)

auxiliary space.

Implementation

Wrap Up

Advanced Topics

Binary Search on Values: An alternative approach is binary searching the actual median value within the range [min(all), max(all)]. This is useful if the arrays are not explicitly stored in memory (e.g., streaming) but can be queried for "count of elements less than X".

K-th Smallest Element: This problem is a specific case of finding the

k

-th smallest element in two sorted arrays. A recursive

O(\log k)

approach can be implemented by discarding

k/2

elements from either array in each step.

Parallelization: While

O(\log N)

is already extremely fast, for massive distributed datasets, one could use a median-of-medians approach or divide the search space across multiple nodes.