Median of Two Sorted Arrays

Problem

You are given two sorted arrays nums1 and nums2 of sizes m and n respectively. Your task is to find the median of the two sorted arrays combined.

The median is the middle value in an ordered list. If the total number of elements is even, the median is the average of the two middle values.

Input Format

• nums1: A sorted integer array of length m
• nums2: A sorted integer array of length n

Output Format

• Return a float representing the median of the two combined sorted arrays, rounded or truncated to at most 5 decimal places.

Examples

Example 1

Input: nums1 = [1, 3], nums2 = [2] Output: 2.0 Explanation: Merged array = [1, 2, 3]. Median is the middle element: 2.

Example 2

Input: nums1 = [1, 2], nums2 = [3, 4] Output: 2.5 Explanation: Merged array = [1, 2, 3, 4]. Median = (2 + 3) / 2 = 2.5.

Example 3

Input: nums1 = [], nums2 = [1] Output: 1.0 Explanation: Only one array has elements. Median of [1] is 1.0.

Approach Hints

Brute Force (O((m+n) log(m+n)))

Merge both arrays into a single sorted array, then compute the median directly. This is straightforward but not optimal.

Optimal Approach — Binary Search (O(log(min(m,n))))

The key insight is to partition both arrays such that:

• Elements on the left side of both partitions combined are ≤ elements on the right side.
• The number of elements on the left equals the number on the right (or is one more for odd totals).

Binary search on the smaller array to find the correct partition point. At a valid partition:

• maxLeft1 <= minRight2
• maxLeft2 <= minRight1

The median is then derived from the boundary elements of the partitions.

Think about:

• What happens when one array is empty?
• How do you handle edge partitions (partition at index 0 or end of array)?
• What do you use as +∞ and -∞ for boundary conditions?