Median of Two Sorted Arrays

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

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)

Binary search a partition in the smaller array so that the left half of both arrays contains exactly half the 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. Ensure nums1 is the smaller array.
2. Let half = (m + n + 1) / 2.
3. Binary search i in nums1, and set j = half - i in nums2.
4. Define left1 = nums1[i-1] (or -inf if i==0), right1 = nums1[i] (or +inf if i==m). Define left2, right2 similarly from nums2.
5. If left1 <= right2 and left2 <= right1, you found the partition:
   • If total length is odd, median is max(left1, left2).
   • Else median is (max(left1, left2) + min(right1, right2)) / 2.
6. If left1 > right2, move left; else move right.

Correctness sketch

• Invariant: at each step, we maintain a valid partition range in the smaller array.
• The valid answer lies within the maintained [lo, hi] range.
• Each comparison discards half the range that cannot contain an answer.
• When the loop ends, the remaining boundary/index is correct.

Trace (hand walkthrough)

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

Walk:
- nums1=[1,3], nums2=[2], half=2
- i=1, j=1: leftA=1 rightA=3 leftB=2 rightB=+inf
- valid partition -> median=max(1,2)=2.0

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.

Complexity

• Time: O(log(min(m, n))).
• Extra space: O(1).

Implementation notes (Go)

• Use large sentinel values (e.g., int64) for -inf/+inf.
• Return float64 even for integer medians.