Median of Sorted Array BS

Find the median of two sorted arrays in O(log(min(n,m))) using binary search.

binary-search arrays median divide-and-conquer

Write a function `find_median_sorted_arrays(nums1, nums2)` that takes two sorted lists of integers `nums1` and `nums2` and returns the median of the combined sorted list as a float.

The combined length is `n = len(nums1) + len(nums2)`. If `n` is odd, the median is the middle element (index `n//2`). If `n` is even, the median is the average of the two middle elements (indices `n//2 - 1` and `n//2`).

Your solution must run in **O(log(min(len(nums1), len(nums2))))** time. You are not allowed to simply concatenate and sort the arrays.

The inputs are already sorted in non-decreasing order. They may be empty (but not both empty — the total length is at least 1). The values are 32-bit integers.

Constraints

- `len(nums1) + len(nums2) >= 1`
- Each input list is sorted in non-decreasing order.
- Item values are within the 32-bit signed integer range.
- Complexity: O(log(min(len(nums1), len(nums2)))) time, O(1) extra space.

Example

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

45 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Focus on the smaller array to minimize binary search iterations.

Use a partition that splits both arrays into left and right halves; compare the max of lefts and min of rights.

Handle edge cases where the partition index is 0 or the full length of an array by using negative/positive infinity.

After finding a valid partition, compute the median based on odd/even total length.

Test Results

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