Median of Two Sorted Arrays

Given two sorted arrays, return the median of the combined dataset in O(log(min(m,n))) time.

Why this is worth learning

Partition the combined rank space rather than merge it. Choose how many entries to take from the smaller array; the required left-side total determines the cut in the other array.

Before coding: one-minute experiment

For A=[1,3] and B=[2], after placing two elements on the left, what are the median boundaries? Why can a finite sentinel such as 2^60 be unsafe?

Function signature

func FindMedianSortedArrays(nums1, nums2 []int) float64

Inputs / outputs

• nums1, nums2: sorted arrays (possibly empty).
• Return: median value as float64.

Example

nums1 = [1,3], nums2 = [2]
Output: 2.0

Constraints

• 0 <= len(nums1), len(nums2) <= 100_000

Core idea (near-solution)

Merging both sorted arrays and reading the middle is an O(m+n) baseline. The median does not require the whole merge: it needs a left set of the correct size whose values are all no greater than the right set. A cut in each input describes that partition. Once the total left count is fixed, one cut determines the other, and only the two cross-boundary comparisons remain to establish order.

Binary search a partition in the smaller array so that the left side contains ceil((m+n)/2) elements and all left values are <= all right values.

Invariant: at each step, we maintain a valid partition range in the smaller array.

Algorithm (step-by-step)

1. If both arrays are empty, return 0 by this pack’s convention. Otherwise swap local array variables if necessary so A is the shorter array, with lengths m<=n.
2. Set half=(m+n+1)/2, lo=0, hi=m. These are cuts, so both 0 and m are candidates.
3. While lo<=hi, choose i=lo+(hi-lo)/2 and j=half-i.
4. If i>0, j<n, and A[i-1]>B[j], set hi=i-1: too many A values are on the left.
5. Otherwise, if j>0, i<m, and B[j-1]>A[i], set lo=i+1: too few A values are on the left.
6. Otherwise the cut is valid. Select the largest existing left boundary. For an odd total, convert it to float64 and return it.
7. For an even total, also select the smallest existing right boundary and return their overflow-safe arithmetic mean. Do not add them as signed ints or convert opposite large operands separately before cancellation. Missing boundaries require conditional reads, not finite sentinels.

Correctness sketch

For cuts i and j with i+j=ceil((m+n)/2), both left portions and both right portions are individually sorted. The partition is globally ordered exactly when each existing left boundary is at most the opposite right boundary. If the first array’s left boundary is too large, decrease its cut; if the second array’s left boundary is too large, increase the first cut. These violations are monotone, so binary search finds a valid partition. For odd size, the largest left boundary is the median; for even size, average that boundary with the smallest right boundary. Missing boundaries are handled by conditions, not finite values pretending to be infinity.

Trace (hand walkthrough)

Input arrays are [1,3] and [2]. Swap local variables first: A=[2], B=[1,3], m=1, n=2, and half=2.

lo	hi	i	j	Evidence	Decision
0	1	0	2	B[j-1]=3 > A[i]=2	lo=1
1	1	1	1	A[i-1]=2 <= B[j]=3; A has no right value	valid cut

The existing left boundaries are 2 and 1, whose maximum is 2. The total is odd, so return 2.0. At the valid cut, never index A[1]: that right boundary is absent.

Pitfalls to avoid

• Not searching the smaller array (can break bounds logic).
• Off-by-one in the partition size.
• Forgetting to handle empty arrays with sentinels.

Debugging lens

Test one empty array, highly unequal lengths, opposite signed extrema, and two very large same-sign boundaries. Do not add the two ints before converting if the sum can overflow. The corrected helper preserves cancellation and exact integer-sum rounding.

Complexity

Time O(log(min(m,n)+1)) and O(1) auxiliary space. The +1 handles an empty smaller array without the undefined log(0) shorthand. The return is the correctly rounded float64 representation of the selected value or arithmetic mean.

Implementation notes (Go)

• Check whether partition boundaries exist; finite sentinels cannot represent infinity for the full int domain.
• Return float64 even for integer medians.

Contract precision

Sorted inputs may be empty. The median of two empty arrays is mathematically undefined, but this pack retains the existing return value 0 for that case. No finite sentinel is assumed to dominate valid int inputs.

Reconstruction checkpoint

For A=[1,3] and B=[2], after placing two elements on the left, what are the median boundaries? Why can a finite sentinel such as 2^60 be unsafe?

Model answer

The valid left set is [1,2] and the right set [3], so the odd median is 2. The API gives no smaller value bound than int, so an actual input can exceed 2^60 and break a comparison that treats it as positive infinity.

Return to Binary Search · Module quiz