Median of Two Sorted Arrays

hard

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m + n)).

Test Cases

Copy an input into the main harness and Run to verify

Input

nums1 = [1,3], nums2 = [2]

Expected Output

2.00000

Explanation: The merged array is [1,2,3] and the median is 2.

Input

nums1 = [1,2], nums2 = [3,4]

Expected Output

2.50000

Explanation: The merged array is [1,2,3,4], so the median is (2 + 3) / 2 = 2.5.

Hint 1 — click to reveal

The median splits the combined values into two halves of equal size — you never need to actually merge them.

Hint 2 — click to reveal

Binary search over how many elements to take from the *shorter* array.

Java Compiler