#leetcode Median of two sorted array

[phuongddx]

Sure, let's dive into the details of the optimized way (binary search) for finding the median of two sorted arrays.

Explanation

The main idea of this approach is to use binary search to partition the two arrays into two halves such that the left half contains the same number of elements as the right half, or one more if the total number of elements is odd. The median will be the average of the maximum element on the left side and the minimum element on the right side if the total number of elements is even. If the total number of elements is odd, the median will be the maximum element on the left side.

Here is a step-by-step explanation:

1. Ensure nums1 is the smaller array:

   • This is done to ensure that the binary search is performed on the smaller array for efficiency. If nums1 is not the smaller array, we swap nums1 and nums2.

2. Initialize variables:

   • m and n are the lengths of nums1 and nums2 respectively.
   • imin and imax are the initial bounds of the binary search range on nums1.
   • half_len is the midpoint of the combined length of the two arrays, adjusted for integer division.

3. Binary search:

   • We perform binary search on nums1. In each iteration, we:
     • Calculate i as the midpoint of the current search range.
     • Calculate j as the index that partitions nums2 such that the total number of elements on the left side of the partition is equal to the total number of elements on the right side.

4. Check partition correctness:

   • If i is too small (nums1[i] < nums2[j - 1]), it means we need more elements on the left side from nums1. So, we move imin to i + 1.
   • If i is too big (nums1[i - 1] > nums2[j]), it means we need fewer elements on the left side from nums1. So, we move imax to i - 1.
   • Otherwise, the partition is correct.

5. Calculate the median:

   • If the partition is correct:
     • Determine the maximum element on the left side (max_of_left).
     • If the total number of elements is odd, return max_of_left as the median.
     • Determine the minimum element on the right side (min_of_right).
     • If the total number of elements is even, return the average of max_of_left and min_of_right as the median.

Here is the code again with inline comments for clarity:

def findMedianSortedArrays(nums1, nums2):
    # Ensure nums1 is the smaller array
    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

        # i is too small, must increase it
        if i < m and nums1[i] < nums2[j - 1]:
            imin = i + 1
        # i is too big, must decrease it
        elif i > 0 and nums1[i - 1] > nums2[j]:
            imax = i - 1
        # i is perfect
        else:
            # Handle edge cases where i or j is 0 or len(nums1) or len(nums2)
            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
nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArrays(nums1, nums2))  # Output: 2.0

nums1 = [1, 2]
nums2 = [3, 4]
print(findMedianSortedArrays(nums1, nums2))  # Output: 2.5

Key Points

• The binary search is performed on the smaller array to minimize the search space.
• The partition ensures that the left half and right half have an equal number of elements.
• Edge cases are handled when i or j are at the boundaries of the arrays.
• The solution achieves the desired time complexity of O(log(min(m, n))).

This optimized approach is efficient and well-suited for scenarios where the arrays are large.