Median of Two Sorted Arrays

Find the median of two sorted arrays with an O(log(min(m,n))) binary search approach.

median binary search arrays divide and conquer

Write a function `median_of_two_sorted_arrays(nums1, nums2)` that takes two sorted integer arrays `nums1` and `nums2` (each sorted in non-decreasing order). The function should return the median of the two arrays combined.

If the total number of elements is odd, return the middle element as a float. If the total number of elements is even, return the average of the two middle elements.

The solution must run in O(log(min(m, n))) time, where m and n are the lengths of `nums1` and `nums2` respectively. Your implementation must use a binary search approach.

**Function signature:**
```python
def median_of_two_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
```

**Examples:**
```python
median_of_two_sorted_arrays([1, 3], [2])         # returns 2.0 (combined [1,2,3], median 2)
median_of_two_sorted_arrays([1, 2], [3, 4])      # returns 2.5 (combined [1,2,3,4], median (2+3)/2)
median_of_two_sorted_arrays([0, 0], [0, 0])      # returns 0.0
median_of_two_sorted_arrays([], [1])             # returns 1.0
```

Constraints

0 <= len(nums1) <= 1000
0 <= len(nums2) <= 1000
len(nums1) + len(nums2) >= 1
-10^6 <= nums1[i], nums2[i] <= 10^6

Your algorithm must have a time complexity of O(log(min(m, n))) and a space complexity of O(1).

Example

>>> median_of_two_sorted_arrays([1, 3], [2])
2.0
>>> median_of_two_sorted_arrays([1, 2], [3, 4])
2.5
>>> median_of_two_sorted_arrays([0, 0], [0, 0])
0.0
>>> median_of_two_sorted_arrays([], [1])
1.0

45 points ~40 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about partitioning the combined array. If you cut the smaller array at index i, where does the cut in the larger array need to be to form two halves?

The left half after partition should contain exactly (m+n+1)//2 elements. Use that to compute the cut position in the second array.

Adjust the binary search range based on whether the left partition of nums1 exceeds the right partition of nums2, and vice versa.

When the partition is perfect, the median is the max of left elements (if odd) or the average of max(left) and min(right) (if even).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.