Median of Two Sorted Arrays

Introduction

Computer science or mathematical applications often require finding the median of two sorted arrays. The median is the middle value when the two arrays are merged and sorted. This median can be found using a variety of algorithms and helps reveal the data's primary tendency.

This guide describes multiple efficient ways to calculate the median of two sorted arrays of varying and equal sizes. We will include programmed examples, outputs, and brief explanations to help you grasp each procedure. With a proper understanding, you will be able to successfully implement these techniques in your programming tasks.

Overview

The median of two sorted arrays is a pivotal value, often used in statistics, data analysis, and algorithm optimization. Efficiently computing this value is crucial for improving performance in various applications. In this article, we will explore different techniques to calculate the median, including merging arrays, binary search, priority queues, and simulated stacks. By the end of this tutorial, you’ll be highly skilled and able to use this versatile and useful tool in a variety of applications. So, let’s get started!

Median of Two Sorted Arrays of Different Sizes by Merging Arrays Efficiently

Concept:

To find the median of two sorted arrays with different sizes, we can merge the arrays virtually using a two-pointer approach without merging them physically. We maintain two pointers, one for each array, and move them accordingly to keep track of the middle elements.

Example:

Output:

Explanation:

- In this example, the code defines a function named `find_median`, which takes two sorted arrays `arr1` and `arr2` as input parameters.

- The function merges the two arrays into a new list called ‘merged', maintaining the sorted order of elements.

- It uses two pointers `i` and `j` to traverse through both arrays `arr1` and `arr2`.

- The merged array contains all elements from `arr1` and `arr2` in sorted order.

- The median is then calculated based on the merged array's length, `n`.

- If the total number of elements in the merged array is even, the median is the average of the two middle elements.

- If the total number of elements is odd, the median is the middle element itself.

- The `find_median` function returns the calculated median, which is printed in the example using the given arrays `[2, 4, 6, 8, 10]` and `[1, 3, 5]`.

- The output will be: `Median: 4`.

Median of Two Sorted Arrays of Different Sizes Using Binary Search

Concept:

To determine the median using binary search, the arrays must be partitioned such that the elements on the left are smaller than the elements on the right. The median is then the average of the largest element on the left and the smallest element on the right.

Example:

Output:

Explanation:

• The Python function find_median requires two sorted arrays, arr1 and arr2, as input.
• The function starts by shifting arr1 to make it smaller.
• Two pointers, low and high, are set up to binary search arr1. The binary search efficiently identifies the partition sites in arr1 and arr2, separating the arrays into two equal-length halves.
• Partition_x and partition_y, representing arr1 and arr2 partition positions, are determined inside the loop.
• The variables max_left_x, min_right_x, max_left_y, and min_right_y store the maximum and minimum elements of partition_x and partition_y in arr1 and arr2.
• If the partition points meet certain parameters, the median is calculated and returned.
• If the arrays are even, the median is the average of the middle two elements. Otherwise, for odd numbers, the median is the greater of the two middle elements.
• In the example employing arrays [2, 4, 6, 8, 10] and [1, 3, 5, 7], find_median prints the determined median.
• The output is 5.0 median.

Median of Two Sorted Arrays of Different Sizes Using Priority Queue

Concept:

We can use a priority queue data structure to merge the two arrays efficiently while maintaining the correct order of elements.

Example:

Output:

Explanation:

In this example, the two sorted arrays are [1, 3, 5, 7] and [2, 4, 6]. We use a priority queue to merge the arrays, and the merged queue becomes [1, 2, 3, 4, 5, 6, 7]. The median is 4.0.

Median of Two Sorted Arrays of Different Sizes Using Simulated Stack

Concept:

The simulated stack performs operations similar to a merge operation in merge sort, helping us find the median effectively.

Example:

def findMedianSortedArrays(arr1, arr2):
    m, n = len(arr1), len(arr2)
    total = m + n
    stack = []

    ptr1, ptr2 = 0, 0

    while len(stack) < total // 2 + 1:
        if ptr1 < m and (ptr2 >= n or arr1[ptr1] < arr2[ptr2]):
            stack.append(arr1[ptr1])
            ptr1 += 1
        else:
            stack.append(arr2[ptr2])
            ptr2 += 1

    if total % 2 == 0:
        return (stack[-1] + stack[-2]) / 2.0
    else:
        return float(stack[-1])

# Example

arr1 = [1, 3, 8, 9, 15]
arr2 = [7, 11, 18, 19, 21, 25]
median = findMedianSortedArrays(arr1, arr2)
print(f"Median: {median}")

Output:

Median: 9.0

The median of these two sorted arrays is 9.0. This is the average of the two middle elements from the merged array: [1, 3, 7, 8, 9, 11, 15, 18, 19, 21], which are 8 and 9.

Explanation:

1. We initialize two pointers, ptr1 for arr1 and ptr2 for arr2, both initially at 0.
2. We create an empty stack to simulate the merging process.
3. We loop until we have added (m + n) / 2 + 1 elements to the stack because we need the middle element(s).
4. In each iteration, we compare the current elements at ptr1 and ptr2 and add the smaller ones to the stack.
5. We then increment the pointer of the array from which we took the element.
6. After the loop, we check if the total number of elements is even or odd and calculate the median accordingly.

Median of Two Sorted Arrays Same Size

Concept:

When both input arrays have the same size, finding the median is relatively straightforward. We can merge the arrays and calculate the median based on the merged result.

Example (using pseudo-code):

Suppose we have two sorted arrays, `arr1` and `arr2`, each of size `n`. We will virtually merge the arrays to find the median.

Example (using values):

Suppose we have two sorted arrays [1, 3, 5] and [2, 4, 6], both with the same size of 3.

• The function virtually merges the arrays by comparing elements at positions i and j and creating the merged list [1, 2, 3, 4, 5, 6].
• As the merged list has an even number of elements (6 elements), the function calculates the median as the average of the two middle elements, which are 3 and 4.
• The median of the merged array is (3 + 4) / 2 = 3.5.

In the above example, the function findMedian efficiently finds the median of the merged array [1, 2, 3, 4, 5, 6], which is 3.5.

Please note that this is a pseudo-code representation of the concept, and you can use similar merging and median calculation steps in any programming language of your choice to find the median of two sorted arrays of the same size.

Median of Two Sorted Arrays in C

Concept:

We can implement various algorithms to find the median of two sorted arrays in C. One common approach is to use a two-pointer technique to virtually merge the arrays.

Example in C:

Output:

Explanation:

• FindMedian requires four parameters: two sorted arrays, arr1 and arr2, and their sizes, size1 and size2.
• A new array of size size1 + size2 stores the merged elements of both arrays.
• Three variables, i, j, and k, are initialized to track arr1, arr2, and combined positions.
• While maintaining the sorted order, a while loop merges arr1 and arr2 into the merged array.
• The loop condition checks if i and j are less than size1 and size2 arrays. The loop terminates if the array is exhausted.
• It compares arr1 and arr2 elements at locations i and j in the loop. The smaller element is added to the merged array and the pointer (i or j) is incremented.
• After merging both arrays, the procedure uses separate while loops to add any remaining elements from arr1 and arr2.
• The middle variable is the index of the middle element in the merged array, calculated as the average of the array sizes (size1 + size2) divided by 2.
• If the merged array has even numbers, the function calculates the median as the average of the two middle members.
• If the merged array has an odd number of elements, the function returns the median as the middle member.
• Two sorted arrays [2, 4, 6] and [1, 3, 5] are defined and their sizes are determined in the main method.
• The findMedian function receives these arrays and sizes.
• The printf function displays the median.
• The output is a median of 3.500000.

Median of Two Sorted Arrays-Divide and Conquer

Concept:

Divide and conquer is a widely used technique to find the median of two sorted arrays efficiently. We partition both arrays and compare the elements around the median to arrive at the answer.

Example:

Output:

Explanation:

• The findMedian method takes two sorted arrays, arr1 and arr2.
• Concatenating and sorting the two arrays with Python's sorted() function creates the list.
• The total number of entries in the merged list is determined as n.
• If n is even, the method calculates the median as the average of the two middle entries at indices (n // 2 - 1) and (n // 2) in the merged list.
• If n is odd, the function calculates the median as the middle element at index n // 2.
• The median is returned by the function.
• The findMedian function receives two sorted arrays [1, 3, 5] and [2, 4, 6].
• The function efficiently returns 3.5 as the median of the merged array [1, 2, 3, 4, 5, 6].
• The output is median: 3.5.

Median of Two Sorted Arrays O(log(m+n)) Time Complexity

Concept:

The divide and conquer algorithm divides two sorted arrays into halves, with smaller elements in the left half. Finding the partition points determines the median of the combined arrays. This approach lowers the search space in logarithmic time (O(log(min(m, n))) and processes even and odd-sized arrays.

Example:

```java
public class MedianOfTwoSortedArrays {


    public static double findMedian(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;


        if (m > n) {
            // Swap the arrays and sizes to ensure nums1 is smaller.
            int[] tempArr = nums1;
            nums1 = nums2;
            nums2 = tempArr;


            int tempSize = m;
            m = n;
            n = tempSize;
        }


        int imin = 0, imax = m, halfLen = (m + n + 1) / 2;


        while (imin <= imax) {
            int i = (imin + imax) / 2;
            int j = halfLen - i;


            if (i < m && nums2[j - 1] > nums1[i]) {
                // i is too small, increase it
                imin = i + 1;
            } else if (i > 0 && nums1[i - 1] > nums2[j]) {
                // i is too big, decrease it
                imax = i - 1;
            } else {
                // i is perfect, get the median
                int maxLeft;
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                } else if (j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }


                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }


                int minRight;
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums1[i], nums2[j]);
                }


                return (maxLeft + minRight) / 2.0;
            }
        }


        return 0.0;
    }


    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8, 10};


        double median = findMedian(arr1, arr2);
        System.out.println("Median: " + median);
    }
}
```

Output:

Explanation:

In this example, we have two sorted arrays, `arr1 = {1, 3, 5, 7}` and `arr2 = {2, 4, 6, 8, 10}`.

The `findMedian` function uses the divide and conquer approach to find the median. After evaluating the arrays, the median is calculated as 5.5.

The time complexity of this algorithm is O(log(min(m, n))), where m and n are the sizes of the two input arrays. The example demonstrates how the divide and conquer technique efficiently finds the median in logarithmic time complexity, even for larger arrays.

Conclusion

The median of two sorted arrays is a fundamental concept with widespread applications. By understanding the efficient techniques we covered—merging arrays, binary search, priority queues, and simulated stacks—you can confidently find the median, regardless of the array sizes. These techniques optimize algorithms and can be applied to various real-world scenarios.

FAQs

Q: When computing the median of two sorted arrays, what happens if one input array is empty?

If one array is empty, the median is the middle element of the non-empty array's odd length. The median of an even-length array is the average of the two middle components. Correct median computation requires empty array handling.

Q: Do I need to sort the array to find the median?

Yes, you must sort the array to find the median. Determine if the array has even or odd elements. Return the array's midpoint if odd. The median is the average of the two middle numbers in all other circumstances.

Q: Which sorted array has the best performance?

Quicksort is the most efficient sorting algorithm for common applications, especially when input array properties are unknown. It beats insertion sort for large lists.