Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median…
- User
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2. Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106
Assistant
Certainly! To find the median of two sorted arrays with a time complexity of O(log(m+n)), we can use a binary search approach. Here's a Python solution that achieves this:
def findMedianSortedArrays(nums1, nums2): # Ensure nums1 is the smaller array to minimize the binary search range if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) imin, imax, half_len = 0, m, (m + n + 1) // 2 while imin <= imax: i = (imin + imax) // 2 j = half_len - i if i < m and nums2[j-1] > nums1[i]: # i is too small, must increase it imin = i + 1 elif i > 0 and nums1[i-1] > nums2[j]: # i is too big, must decrease it imax = i - 1 else: # i is perfect if i == 0: max_of_left = nums2[j-1] elif j == 0: max_of_left = nums1[i-1] else: max_of_left = max(nums1[i-1], nums2[j-1]) if (m + n) % 2 == 1: return max_of_left if i == m: min_of_right = nums2[j] elif j == n: min_of_right = nums1[i] else: min_of_right = min(nums1[i], nums2[j]) return (max_of_left + min_of_right) / 2.0 # Example usage: print(findMedianSortedArrays([1, 3], [2])) # Output: 2.0 print(findMedianSortedArrays([1, 2], [3, 4])) # Output: 2.5Explanation:
-
Ensure
nums1is the Smaller Array:- We start by ensuring that
nums1is the smaller of the two arrays. This optimisation helps to reduce the range of our binary search, making the algorithm more efficient.
- We start by ensuring that
-
Initialise Variables:
iminandimaxare initialised to0and the length ofnums1(m), respectively. These variables will help us perform the binary search onnums1.half_lenis calculated as(m + n + 1) // 2. This represents the combined half-length of both arrays, which helps us to find the partition.
-
Binary Search Loop:
- We perform a binary search on
nums1to find the correct partitioni. iis calculated as the midpoint betweeniminandimax.jis then calculated ashalf_len - i, which gives us the corresponding partition innums2.
- We perform a binary search on
-
Adjust Partitions:
- If
iis too small (i.e.,nums1[i]is less thannums2[j - 1]), we need to increasei, so we setimintoi + 1. - If
iis too large (i.e.,nums1[i - 1]is greater thannums2[j]), we need to decreasei, so we setimaxtoi - 1. - If
iis perfect, we proceed to calculate the median.
- If
-
Calculate the Median:
max_of_leftis the maximum value of the left partition.min_of_rightis the minimum value of the right partition.- If the total number of elements
(m + n)is odd the median ismax_of_left. - If
(m + n)is even, the median is the average ofmax_of_leftandmin_of_right
This algorithm ensures that we find the median in O(log(min(m, n))) time, which satisfies the O(log(m+n)) complexity requirement.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.