Smart Sorting: Finding the Middle Number of Two Ordered Lists

Article

This C# code aims to find the median of two sorted arrays efficiently using a binary search approach. The FindMedianSortedArrays method intelligently partitions the arrays to locate the middle elements, considering various edge cases. The logic ensures a logarithmic runtime complexity of O(log(min(m, n))). The example usage in the Main method demonstrates how the function works with two sets of sorted arrays, providing a median value for each.

using System;

public class Solution
{
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        // Check if the first array is longer than the second one; if so, swap them
        if (nums1.Length > nums2.Length)
        {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        // Get the lengths of the two arrays
        int x = nums1.Length;
        int y = nums2.Length;

        // Initialize the low and high pointers for binary search
        int low = 0;
        int high = x;

        // Perform binary search
        while (low <= high)
        {
            // Calculate the partition points for both arrays
            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;

            // Determine the maximum and minimum values on both sides of the partition
            int maxX = (partitionX == 0) ? int.MinValue : nums1[partitionX - 1];
            int minX = (partitionX == x) ? int.MaxValue : nums1[partitionX];
            int maxY = (partitionY == 0) ? int.MinValue : nums2[partitionY - 1];
            int minY = (partitionY == y) ? int.MaxValue : nums2[partitionY];

            // Check if the current partition is valid
            if (maxX <= minY && maxY <= minX)
            {
                // If the total number of elements is even, return the average of the middle elements
                if ((x + y) % 2 == 0)
                {
                    return (Math.Max(maxX, maxY) + Math.Min(minX, minY)) / 2.0;
                }
                // If the total number of elements is odd, return the larger of the two middle elements
                else
                {
                    return Math.Max(maxX, maxY);
                }
            }
            // Adjust the partition based on the comparison of maxX and minY
            else if (maxX > minY)
            {
                high = partitionX - 1;
            }
            else
            {
                low = partitionX + 1;
            }
        }

        // If the input arrays are not sorted, throw an exception
        throw new InvalidOperationException("Input arrays are not sorted.");
    }

    // Example usage:
    static void Main()
    {
        // Create an instance of the Solution class
        Solution solution = new Solution();

        // Example 1
        int[] nums1 = { 1, 3 };
        int[] nums2 = { 2 };
        double result1 = solution.FindMedianSortedArrays(nums1, nums2);
        Console.WriteLine(result1);  // Output: 2.0

        // Example 2
        int[] nums3 = { 1, 2 };
        int[] nums4 = { 3, 4 };
        double result2 = solution.FindMedianSortedArrays(nums3, nums4);
        Console.WriteLine(result2);  // Output: 2.5
    }
}