find_median_sorted_arrays()

Find the median of two sorted arrays using binary search.

Implementation

Args: nums1: First sorted array nums2: Second sorted array Returns: The median value

Example

find_median_sorted_arrays([1.0, 2.0], [3.0, 4.0])

Expected output: 2.5

Source Code

                        def find_median_sorted_arrays(nums1: List[float], nums2: List[float]) -> float:
    # Ensure nums1 is the smaller array for binary search efficiency
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    total_length = m + n
    half_length = (total_length + 1) // 2  # For handling both odd/even cases

    left, right = 0, m

    while left <= right:
        partition1 = (left + right) // 2
        partition2 = half_length - partition1

        maxLeft1 = float("-inf") if partition1 == 0 else nums1[partition1 - 1]
        minRight1 = float("inf") if partition1 == m else nums1[partition1]

        maxLeft2 = float("-inf") if partition2 == 0 else nums2[partition2 - 1]
        minRight2 = float("inf") if partition2 == n else nums2[partition2]

        # Check if we've partitioned correctly
        if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
            # If odd, return the max of the left halves
            if total_length % 2 == 1:
                return max(maxLeft1, maxLeft2)
            # If even, return the average of the two middle values
            return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
        elif maxLeft1 > minRight2:
            # Move towards left in nums1
            right = partition1 - 1
        else:
            # Move towards right in nums1
            left = partition1 + 1

    return 0
                    