Median of Two Sorted Arrays

Hard

The problem

You get two lists of numbers, each already sorted from smallest to biggest. Imagine merging them into one sorted list and return its median: the middle number, or the average of the two middle numbers if the merged list has an even length.

Example 1
Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
Merged: [1, 2, 3]. The middle number is 2.
Example 2
Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5
Merged: [1, 2, 3, 4]. The middle numbers are 2 and 3, and their average is 2.5.
Example 3
Input: nums1 = [], nums2 = [5]
Output: 5.0
The merged list is just [5].

Limits

0 ≤ nums1.length, nums2.length ≤ 1,000,000
1 ≤ nums1.length + nums2.length (they are not both empty)
Each list is sorted in non-decreasing order

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

The median splits all numbers into a left half and a right half. Can you binary-search the split point in the SHORTER array?

The idea

Binary search how many elements the short array contributes to the left half; the rest comes from the other array. A split is valid when maxLeftA ≤ minRightB and maxLeftB ≤ minRightA.

Target: O(log(min(m,n))) time

Go function shape

func findMedianSortedArrays(nums1 []int, nums2 []int) float64

Reference solution

Tested with go test. Try it yourself first, then compare.

// FindMedianSortedArrays: binary-search how many elements the SHORTER array puts in the left half.
// A split is correct when everything on the left is <= everything on the right.
func FindMedianSortedArrays(a, b []int) float64 {
	if len(a) > len(b) {
		a, b = b, a
	}
	const inf = 1 << 60
	half := (len(a) + len(b) + 1) / 2
	lo, hi := 0, len(a)
	for lo <= hi {
		i := (lo + hi) / 2 // elements taken from a
		j := half - i      // elements taken from b
		aLeft, aRight, bLeft, bRight := -inf, inf, -inf, inf
		if i > 0 {
			aLeft = a[i-1]
		}
		if i < len(a) {
			aRight = a[i]
		}
		if j > 0 {
			bLeft = b[j-1]
		}
		if j < len(b) {
			bRight = b[j]
		}
		switch {
		case aLeft > bRight:
			hi = i - 1 // took too many from a
		case bLeft > aRight:
			lo = i + 1 // took too few from a
		default:
			leftMax := max(aLeft, bLeft)
			if (len(a)+len(b))%2 == 1 {
				return float64(leftMax)
			}
			return float64(leftMax+min(aRight, bRight)) / 2
		}
	}
	return 0
}

Read the lesson: Binary Search