Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays. The solution must use binary search to achieve an overall run time complexity of O(log(min(m,n))), where m and n are the lengths of nums1 and nums2 respectively.
Input: nums1 = [1,3], nums2 = [2]
Output: 2.0
Explanation: The merged array is [1,2,3] and the median is 2.
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.5
Explanation: The merged array is [1,2,3,4] and the median is (2+3)/2 = 2.5.
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.0
Explanation: The merged array consists of all zeros, so the median is 0.0.
The median partitions the combined sorted array into two halves of equal size (or differing by one). By binary searching on the smaller array, we can find a partition where all elements on the left are less than or equal to all on the right. This allows us to compute the median in O(log(min(m,n))) time without merging the arrays.
nums1 is the smaller array (swap if necessary).m = len(nums1), n = len(nums2). Binary search on i in [0, m]. For each i, compute j = (m+n+1)//2 - i.left1 = (i==0) ? -∞ : nums1[i-1]left2 = (j==0) ? -∞ : nums2[j-1]right1 = (i==m) ? +∞ : nums1[i]right2 = (j==n) ? +∞ : nums2[j]left1 <= right2 and left2 <= right1, correct partition found. Then:
max(left1, left2).(max(left1, left2) + min(right1, right2)) / 2.left1 > right2, move high = i-1.low = i+1.#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int m = nums1.size(), n = nums2.size();
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
int low = 0, high = m;
while (low <= high) {
int i = (low + high) / 2;
int j = (m + n + 1) / 2 - i;
int left1 = (i == 0) ? INT_MIN : nums1[i-1];
int left2 = (j == 0) ? INT_MIN : nums2[j-1];
int right1 = (i == m) ? INT_MAX : nums1[i];
int right2 = (j == n) ? INT_MAX : nums2[j];
if (left1 <= right2 && left2 <= right1) {
if ((m + n) % 2 == 1) {
return (double)max(left1, left2);
} else {
return (max(left1, left2) + min(right1, right2)) / 2.0;
}
} else if (left1 > right2) {
high = i - 1;
} else {
low = i + 1;
}
}
return 0.0;
}
}; import java.util.*;
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
int low = 0, high = m;
while (low <= high) {
int i = (low + high) / 2;
int j = (m + n + 1) / 2 - i;
int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i-1];
int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j-1];
int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (left1 <= right2 && left2 <= right1) {
if ((m + n) % 2 == 1) {
return (double)Math.max(left1, left2);
} else {
return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
}
} else if (left1 > right2) {
high = i - 1;
} else {
low = i + 1;
}
}
return 0.0;
}
}from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m, n = len(nums1), len(nums2)
if m > n:
return self.findMedianSortedArrays(nums2, nums1)
low, high = 0, m
while low <= high:
i = (low + high) // 2
j = (m + n + 1) // 2 - i
left1 = float('-inf') if i == 0 else nums1[i-1]
left2 = float('-inf') if j == 0 else nums2[j-1]
right1 = float('inf') if i == m else nums1[i]
right2 = float('inf') if j == n else nums2[j]
if left1 <= right2 and left2 <= right1:
if (m + n) % 2 == 1:
return max(left1, left2)
else:
return (max(left1, left2) + min(right1, right2)) / 2.0
elif left1 > right2:
high = i - 1
else:
low = i + 1
return 0.0function findMedianSortedArrays(nums1, nums2) {
let m = nums1.length, n = nums2.length;
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
let low = 0, high = m;
while (low <= high) {
let i = Math.floor((low + high) / 2);
let j = Math.floor((m + n + 1) / 2) - i;
let left1 = (i === 0) ? -Infinity : nums1[i-1];
let left2 = (j === 0) ? -Infinity : nums2[j-1];
let right1 = (i === m) ? Infinity : nums1[i];
let right2 = (j === n) ? Infinity : nums2[j];
if (left1 <= right2 && left2 <= right1) {
if ((m + n) % 2 === 1) {
return Math.max(left1, left2);
} else {
return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
}
} else if (left1 > right2) {
high = i - 1;
} else {
low = i + 1;
}
}
return 0.0;
}Time Complexity: O(log(min(m,n))), because we perform binary search on the smaller array.
Space Complexity: O(1), as we only use a few extra variables.
Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.