Find the median value of two sorted arrays without fully merging them.
You are given two sorted integer arrays. Your task is to compute the median of the combined multiset formed by all elements from both arrays.
The solution should be more efficient than merging the arrays into one full sorted array when possible. The median is the middle value in the sorted order, or the average of the two middle values when the total number of elements is even.
Input Format
- Two sorted integer arrays,
nums1andnums2. - Arrays may have different lengths and may contain duplicate values.
- Either array may be empty.
Output Format
- Return the median of all values from both arrays.
- If the total number of elements is odd, return the single middle value.
- If the total number of elements is even, return the average of the two middle values.
Constraints
- Each input array is sorted in non-decreasing order.
- At least one array is non-empty.
- Use a solution that is better than linear merge in time complexity when possible.
Example 1
Input
nums1 = [1, 3] nums2 = [2]
Output
2.0
Explanation
The merged order is [1, 2, 3]. The middle value is 2.
Example 2
Input
nums1 = [1, 2] nums2 = [3, 4]
Output
2.5
Explanation
The merged order is [1, 2, 3, 4]. The median is the average of 2 and 3, which is 2.5.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.