How can I efficiently find the median of two sorted arrays in C# without using extra space?
Can someone help me understand I'm dealing with I'm sure I'm missing something obvious here, but I'm trying to implement a function to find the median of two sorted arrays in C#... I want this to be done in a time complexity of O(log(min(n, m))) where n and m are the sizes of the two arrays. However, I'm working with issues when dealing with arrays of different sizes and when the combined length is even versus odd. Here's what I've tried so far: ```csharp public double FindMedianSortedArrays(int[] nums1, int[] nums2) { int totalLength = nums1.Length + nums2.Length; int half = totalLength / 2; int[] merged = new int[totalLength]; Array.Copy(nums1, merged, nums1.Length); Array.Copy(nums2, 0, merged, nums1.Length, nums2.Length); Array.Sort(merged); if (totalLength % 2 == 0) { return (merged[half - 1] + merged[half]) / 2.0; } else { return merged[half]; } } ``` This implementation works fine for smaller arrays, but it becomes inefficient with larger input sizes due to the sorting step. When I run the function with `nums1 = new int[] {1, 3}` and `nums2 = new int[] {2}`, it returns `2.0`, which is correct. But when I use `nums1 = new int[] {1, 2}` and `nums2 = new int[] {3, 4}`, I get `2.5`, which is also correct, but I feel the approach is not optimal. I've also come across a runtime behavior that seems to involve index out-of-bounds when the arrays are unevenly sized. For example, if `nums1` is empty and `nums2` contains multiple elements, the logic I've implemented fails. How can I refactor my code to resolve these issues and maintain efficiency? Any insights on avoiding extra space usage and handling these edge cases would be greatly appreciated. For context: I'm using C# on Ubuntu. What am I doing wrong? How would you solve this? I'm using C# stable in this project. Is there a simpler solution I'm overlooking? This is happening in both development and production on Ubuntu 20.04. Cheers for any assistance!