Median of Two Sorted Arrays

Tagged: Binary Search, Searching, Divide and Conquer, Median-Finding, Two Pointers

Problem

Given two sorted arrays, our task is to find the median of the two sorted arrays. For example,

Input: arr1 = [1,3,8,9,15], arr2 = [7,11,18,19,21,25]
Output: 11
Explanation: merged array = [1,3,7,8,9,11,15,18,19,21,25], median = 11

Input: arr1 = [11,16,23,26], arr2 = [3,5,7,9,31,35]
Output: 13.5
Explanation: merged array = [3,5,7,9,11,16,23,26,31,35], median = 13.5

Solution

Linear Search using Two Pointers

public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
    int n1 = nums1.Length;
    int n2 = nums2.Length;
    int totalLength = n1 + n2;
    int i = 0;
    int j = 0;
    int m1 = -1;
    int m2 = -1;
    int medianLength = totalLength % 2 == 0
        ? (totalLength + 1) / 2
        : totalLength / 2;
    for (int count = 0; count <= medianLength; count++)
    {
        m2 = m1;

        if (i != n1 && j != n2)
        {
            m1 = (nums1[i] > nums2[j]) 
                ? nums2[j++] 
                : nums1[i++];
        }
        else if (i < n1)
        {
            m1 = nums1[i++];
        }
        else
        {
            m1 = nums2[j++];
        }
    }

    double median = totalLength % 2 == 0
        ? (m1 + m2) / 2.0
        : m1;

    return median;
}

Merge both Arrays First

public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
    int[] nums3 = new int[nums1.Length + nums2.Length];
    Array.Copy(nums1, 0, nums3, 0, nums1.Length);
    Array.Copy(nums2, 0, nums3, nums1.Length, nums2.Length);

    Array.Sort(nums3);

    double median;
    if (nums3.Length % 2 == 0)
    {
        int midIndex = nums3.Length / 2;
        int med1 = nums3[midIndex - 1];
        int med2 = nums3[midIndex];
        median = (med1 + med2) / 2.0;
    }
    else
    {
        median = nums3[nums3.Length / 2];
    }

    return median;
}

Binary Search

public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
    if (nums1.Length > nums2.Length)
        return FindMedianSortedArrays(nums2, nums1);

    int nums1Length = nums1.Length;
    int nums2Length = nums2.Length;

    int low = 0;
    int high = nums1.Length;
    while (low <= high)
    {
        int partitionNums1 = (low + high) / 2;
        int partitionNums2 = (nums1Length + nums2Length + 1) / 2 - partitionNums1;

        int nums1MaxLeftNums1 = partitionNums1 == 0 ? int.MinValue : nums1[partitionNums1 - 1];
        int nums2MaxLeftNums2 = partitionNums2 == 0 ? int.MinValue : nums2[partitionNums2 - 1];
        int nums1MinRightNums1 = partitionNums1 == nums1Length ? int.MaxValue : nums1[partitionNums1];
        int nums2MinRightNums2 = partitionNums2 == nums2Length ? int.MaxValue : nums2[partitionNums2];

        if (nums1MaxLeftNums1 <= nums2MinRightNums2 && nums2MaxLeftNums2 <= nums1MinRightNums1)
        {
            if ((nums1Length + nums2Length) % 2 == 0)
                return (Math.Max(nums1MaxLeftNums1, nums2MaxLeftNums2) +
                        Math.Min(nums1MinRightNums1, nums2MinRightNums2)) / 2d;
            else
                return Math.Max(nums1MaxLeftNums1, nums2MaxLeftNums2);
        }

        if (nums1MaxLeftNums1 > nums2MinRightNums2)
        {
            high = partitionNums1 - 1;
        }
        else if (nums2MaxLeftNums2 > nums1MinRightNums1)
        {
            low = partitionNums1 + 1;
        }
    }

    return 0d;
}

Median of Two Sorted Arrays

Problem#

Solution#

Linear Search using Two Pointers#

Merge both Arrays First#

Binary Search#

Problem

Solution

Linear Search using Two Pointers

Merge both Arrays First

Binary Search