Median of Two Sorted Arrays
Problem statement
You are given two sorted arrays $A$ of length $m$ and $B$ of length $n$ (both in non-decreasing order, possibly containing duplicates, possibly empty, not necessarily the same length, and not both empty). Find the median of the combined sorted array of $m + n$ elements.
Implement the function with signature find_median_sorted_arrays(A, B) that returns the median as a float.
Constraints:
- $0 \le m, n \le 10^5$
- Elements can be any integers (including duplicates)
- Required time complexity: $O(\log \min(m, n))$
- Required space complexity: $O(1)$
Examples:
- $A = [1, 3]$, $B = [2]$ -- combined sorted: $[1, 2, 3]$ -- median: $2$
- $A = [1, 2]$, $B = [3, 4]$ -- combined sorted: $[1, 2, 3, 4]$ -- median: $(2 + 3)/2 = 2.5$
- $A = [0, 0]$, $B = [0, 0]$ -- median: $0.0$
Provide the partition-based algorithm, explain why it is correct, and handle both even and odd total lengths.
Example
find_median_sorted_arrays([1, 2], [3, 4]) -> 2.5
The combined sorted array is $[1, 2, 3, 4]$; with an even total of 4 elements the median is the average of the two middle values $(2 + 3) / 2 = 2.5$, returned as a float.
Show hint
Instead of building the merged array, what property must a cut through both arrays have for everything on its left to precede everything on its right?
Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.