Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays. The overall runtime complexity must be O(log(m+n)).
Input: nums1=[1,3], nums2=[2] → Output: 2.0Input: nums1=[1,2], nums2=[3,4] → Output: 2.5
Binary search on the smaller array to find the correct partition. A valid partition satisfies: left1 <= right2 and left2 <= right1. Then compute median from the boundary elements.
- Binary search on the smaller array (make nums1 the smaller).
- Partition i in nums1 and j=(m+n+1)/2-i in nums2.
- Valid if nums1[i-1]<=nums2[j] and nums2[j-1]<=nums1[i].
- Compute median from maxLeft and minRight boundary elements.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
int m = nums1.length, n = nums2.length;
int lo = 0, hi = m;
while (lo <= hi) {
int i = lo + (hi - lo) / 2;
int j = (m + n + 1) / 2 - i;
int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
int maxLeft = Math.max(maxLeft1, maxLeft2);
int minRight = Math.min(minRight1, minRight2);
if ((m + n) % 2 == 1) return maxLeft;
return (maxLeft + minRight) / 2.0;
} else if (maxLeft1 > minRight2) hi = i - 1;
else lo = i + 1;
}
return 0;
}
}
- Time Complexity: O(log(min(M,N)))
- Space Complexity: O(1)