$$ \newcommand\Tr{\mathrm{Tr}} \newcommand{\braket}[2]{\langle #1 \mid #2 \rangle} \newcommand\I{\mathbb{I}} \newcommand{\avg}[1]{\left< #1 \right>} \newcommand{\RD}{D} \newcommand{\ri}{\mathrm{i}} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\Sign}{Sign} \newcommand{\ii}{\mathrm i} \newcommand{\vv}{\mathrm v} \newcommand{\ff}{\mathrm f} \newcommand{\mm}{\mathrm m} \newcommand{\ee}{\mathrm e} \newcommand{\xx}{\mathrm x} \newcommand{\RR}{\mathrm R} \newcommand{\dd}{\mathrm d} \newcommand{\FF}{\mathrm F} \newcommand{\BB}{\mathrm B} \newcommand{\vph}{v_{\mathrm{ph}}} $$

Median of Two Sorted Arrays

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;
}

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;
}