Median of Two Sorted Arrays
My C# solution to LeetCode problem #4:
There are two sorted arrays nums1 and nums2 of size $ m $ and $ n $ respectively. Find the median of the two sorted arrays. The overall run time complexity should be $ O(\log(m+n)) $.
I decided to publish it as solutions I found online are mostly wrong.
public class Solution { private double MedianInSortedArray(int[] nums, int start, int end) { int length = end - start; // Even length, return the average of the two middle elements if (this.Even(length)) { return this.Median2(nums[start + length / 2 - 1], nums[start + length / 2]); } // Odd length, return the middle element return nums[start + length / 2]; } private double Median2(int num1, int num2) { return (num1 + num2) / 2.0; } private double Median3(int num1, int num2, int num3) { int min = Math.Min(Math.Min(num1, num2), num3); int max = Math.Max(Math.Max(num1, num2), num3); return num1 + num2 + num3 - min - max; } private double Median4(int num1, int num2, int num3, int num4) { int lowMid = Math.Max(Math.Min(num1, num2), Math.Min(num3, num4)); int uppMid = Math.Min(Math.Max(num1, num2), Math.Max(num3, num4)); return this.Median2(lowMid, uppMid); } private bool Even(int num) { return (num % 2 == 0); } private double FindMedianSortedArrays(int[] nums1, int nums1Start, int nums1End, int[] nums2, int nums2Start, int nums2End) { int nums1Len = nums1End - nums1Start; int nums2Len = nums2End - nums2Start; // Make sure always nums1Len <= nums2Len to make code shorter if (nums1Len > nums2Len) { return this.FindMedianSortedArrays(nums2, nums2Start, nums2End, nums1, nums1Start, nums1End); } // Handle special cases if (nums1Len == 0 && nums2Len == 0) { return 0.0; } else if (nums1Len == 0) { return this.MedianInSortedArray(nums2, nums2Start, nums2End); } // Get both medians double median1 = this.MedianInSortedArray(nums1, nums1Start, nums1End); double median2 = this.MedianInSortedArray(nums2, nums2Start, nums2End); // Lower and upper median positions; in case of odd lengths equal int lowMid1 = nums1Start + (nums1Len - 1) / 2; int lowMid2 = nums2Start + (nums2Len - 1) / 2; int uppMid1 = nums1Start + nums1Len / 2; int uppMid2 = nums2Start + nums2Len / 2; // If both medians equal, then they are the median of the merged array if (median1 == median2) { return median1; } // BASE CASES if (nums1Len == 1) { if (nums2Len == 1) { return this.Median2(nums1[nums1Start], nums2[nums2Start]); } if (this.Even(nums2Len)) { // The median is lowMid or uppMid in nums2 or it is the only number in nums1 return this.Median3(nums2[lowMid2], nums2[uppMid2], nums1[nums1Start]); } // nums2Len odd, the median is calculated using the three numbers // around the median and the only number in nums1 return this.Median4(nums2[uppMid2 - 1], nums2[uppMid2], nums2[uppMid2 + 1], nums1[nums1Start]); } else if (nums1Len == 2) { // Only four elements, take their median directly if (nums2Len == 2) { return this.Median4(nums1[lowMid1], nums1[uppMid1], nums2[lowMid2], nums2[uppMid2]); } // Length of nums2 is even if (this.Even(nums2Len)) { return this.Median4(nums2[uppMid2], nums2[lowMid2], Math.Max(nums2[uppMid2 - 2], nums1[uppMid1]), Math.Min(nums2[uppMid2 + 1], nums1[lowMid1])); } // Length of nums2 is odd return this.Median3(nums2[uppMid2], Math.Max(nums2[uppMid2 - 1], nums1[uppMid1]), Math.Min(nums2[uppMid2 + 1], nums1[lowMid1])); } // We can't take medians here, as that would discard numbers possibly // involved in the median in the even case int mid1 = nums1[lowMid1]; int mid2 = nums2[lowMid2]; // Reduce the size of bot arrays by the same to prevent median shift int nums1LowHalfLen = (nums1Len - 1) / 2; // Recurse to nums1[start + nums1LowHalfLen ... end], nums2[start ... end - nums1LowHalfLen] if (mid1 < mid2) { return this.FindMedianSortedArrays(nums1, nums1Start + nums1LowHalfLen, nums1End, nums2, nums2Start, nums2End - nums1LowHalfLen); } // Recurse to nums1[start ... end - nums1LowHalfLen], nums2[start + nums1LowHalfLen ... end] return this.FindMedianSortedArrays(nums1, nums1Start, nums1End - nums1LowHalfLen, nums2, nums2Start + nums1LowHalfLen, nums2End); } public double FindMedianSortedArrays(int[] nums1, int[] nums2) { return this.FindMedianSortedArrays(nums1, 0, nums1.Length, nums2, 0, nums2.Length); } }