The Question

Median of Two Sorted Arrays

Given two separate, sorted data collections, design an 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 are the constraints on the input array sizes $m$ and $n$? (Assumption:

0 \le m, n \le 1000

and

1 \le m+n \le 2000

Can both arrays be empty simultaneously? (Assumption: No, at least one array will contain elements).

What is the required time complexity? (Assumption: The standard expectation for this problem is

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

to demonstrate an understanding of binary search over partitions).

What should be returned if the combined length is even vs. odd? (Assumption: If even, return the average of the two middle elements; if odd, return the single middle element).

Thinking Process

Binary Search on Partitions: Instead of merging the arrays, we aim to find a partition point in both arrays such that the left half of the combined set contains the same number of elements as the right half (or one more if the total count is odd).

The "Smaller Array" Optimization: Perform the binary search on the smaller of the two arrays to ensure the search space is minimized and to avoid index-out-of-bounds errors when calculating the corresponding partition in the larger array.

Validating the Partition: A partition is valid if the largest element on the left side of the partition in both arrays is less than or equal to the smallest element on the right side of the partition in both arrays (

L_1 \le R_2

and

L_2 \le R_1

Handling Edge Cases: Use Integer.MIN_VALUE and Integer.MAX_VALUE to handle cases where a partition falls at the very beginning or end of an array, effectively representing "no elements" on that side.

Implementation Breakdown

Problem Set

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

Performance Constraints: Must run in

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

time.

Input Types: Two sorted integer arrays.

Output Type: A double representing the median.

Approach

Algorithm: Binary Search on the partition index.

Data Structure: Primitive Arrays.

Complexity:

Time:

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

where

m

and

n

are lengths of the arrays.

Space:

O(1)

as we only store a constant number of pointers.