Median of Two Sorted Arrays (C++, Java, Python)

The problem of finding the median of two sorted arrays is a classic algorithmic challenge that has intrigued computer scientists, mathematicians, and programmers for years. In this article, we will solve the leetcode problem of How to Find the Median of Two Sorted Arrays using two different approaches.

What is the Median of a Sorted Array?

The median of an array is referred to as the center element of the sorted array. There can be two cases of finding it:

If the array contains an odd number of elements, the median is the middle element in the sorted array.
If the array has an even number of elements, the median is the average of the two middle elements in the sorted array.

Let us take a simple example.

Consider the array {1, 2, 3, 4, 5}.

Since the array is of odd length, the median of the array is simply the middle element that is, 3.

Naive Approach

Before delving into the optimized approach, let’s briefly discuss the naive approach and its limitations. The naive approach involves merging the two sorted arrays into a single array and then finding the median of the merged array.

Since the arrays are already sorted, we will simply maintain two pointers at the initial of both arrays move them accordingly, and add them into the new merged array.

We will maintain two pointers and keep them at the 0th index of both arrays.

We will then compare the integers add the smaller integer into the merged array and move the pointer one index ahead

add the smaller integer into the merged array

Similarly, we will traverse both arrays and make the merged array.
Once the merged array is formed we will find the median of the array as discussed above.
Therefore, the median = 4+5/2 = 4

This approach has a time complexity of O(n+k) as we need to traverse both arrays to merge them and then find the median. Since we are taking an extra array of size n+k, the space complexity is O(n+k).

Optimized Approach

The optimized approach is based on the concept of divide and conquer, similar to binary search. The main idea is to divide the arrays into two parts and compare the medians of both arrays. Based on the comparison, we can discard certain elements and narrow down the search space until we find the median.

Let’s get into the depth with an example:

Array1 = {1, 3, 7, 8}

Array2 = {2, 4, 6}

Given the two arrays, let us try to find our answer.

The combined length of the arrays is 3+4 = 7.
Therefore, we know that our median will be at the 7/2 = 4th position of the merged array.
Let us try not to use extra space and apply the divide and conquer algorithm.
We will try to form symmetric spaces keeping 3 elements in left space and 4 elements in the right space.
Since the length of the second is 3, we can determine that there must be at least 1 element of the array 1 in the left space.

Thus, considering array 1, it can have between 0 to 6 elements.
We will thus apply a Binary search to figure out how many elements to select from array 1.
Low = 0, High = 3. So, mid = 2.
Now we will update the mid as follows:

If L1>R1, high = mid – 1.
If L2>R2, low = mid+1.

Here, we can see that both L1 and L2 are lesser than R1 and R2. Therefore, the left and right segments are sorted.
Now, we can find the median at min(R1, R2)

C++ Code

Here is the C++ program to find median of two sorted arrays using an optimized approach:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    // Ensure nums1 is the smaller array
    if (nums1.size() > nums2.size()) {
        swap(nums1, nums2);
    }

    int m = nums1.size();
    int n = nums2.size();
    int left = 0, right = m, partitionX, partitionY;
    
    while (left <= right) {
        // Choose a partition index in the smaller array nums1
        partitionX = (left + right) / 2;
        // Calculate the corresponding partition index in nums2
        partitionY = (m + n + 1) / 2 - partitionX;
        
        // Calculate maximum and minimum values in the left and right partitions
        int maxX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
        int maxY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
        int minX = (partitionX == m) ? INT_MAX : nums1[partitionX];
        int minY = (partitionY == n) ? INT_MAX : nums2[partitionY];
        
        // Check if the partitions are correct
        if (maxX <= minY && maxY <= minX) {
            // Calculate the median
            if ((m + n) % 2 == 0) {
                return (max(maxX, maxY) + min(minX, minY)) / 2.0;
            } 
          	else {
                return max(maxX, maxY);
            }
        }
      	else if (maxX > minY) {
            // Adjust the partition indexes
            right = partitionX - 1;
        } 
      	else {
            left = partitionX + 1;
        }
    }
    
    return 0.0;  // Return 0.0 if no median found
}

int main() {
    vector<int> nums1 = {1, 3, 7, 8};
    vector<int> nums2 = {2, 4, 6};
    double median = findMedianSortedArrays(nums1, nums2);
    cout << "Median: " << median << endl;
    return 0;
}

Python Code

Below is the Python program using an optimized approach:

def findMedianSortedArrays(nums1, nums2):
    # Ensure nums1 is the smaller array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    left, right, partitionX, partitionY = 0, m, 0, 0

    while left <= right:
        # Choose a partition index in the smaller array nums1
        partitionX = (left + right) // 2
        # Calculate the corresponding partition index in nums2
        partitionY = (m + n + 1) // 2 - partitionX

        # Calculate maximum and minimum values in the left and right partitions
        maxX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
        maxY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
        minX = float('inf') if partitionX == m else nums1[partitionX]
        minY = float('inf') if partitionY == n else nums2[partitionY]

        # Check if the partitions are correct
        if maxX <= minY and maxY <= minX:
            # Calculate the median
            if (m + n) % 2 == 0:
                return (max(maxX, maxY) + min(minX, minY)) / 2.0
            else:
                return float(max(maxX, maxY))
        elif maxX > minY:
            # Adjust the partition indexes
            right = partitionX - 1
        else:
            left = partitionX + 1

    return 0.0  # Return 0.0 if no median found

nums1 = [1, 3, 7, 8]
nums2 = [2, 4, 6]
median = findMedianSortedArrays(nums1, nums2)
print("Median:", median)

Java Code

Check the Java program below to find the median of two sorted arrays:

public class MedianOfTwoSortedArrays {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.length;
        int n = nums2.length;
        int left = 0;
        int right = m;
        int partitionX, partitionY;

        while (left <= right) {
            // Choose a partition index in the smaller array nums1
            partitionX = (left + right) / 2;
            // Calculate the corresponding partition index in nums2
            partitionY = (m + n + 1) / 2 - partitionX;

            // Calculate maximum and minimum values in the left and right partitions
            int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];
            int minY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];

            // Check if the partitions are correct
            if (maxX <= minY && maxY <= minX) {
                // Calculate the median
                if ((m + n) % 2 == 0) {
                    return (double) (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;
                } 
              	else {
                    return (double) Math.max(maxX, maxY);
                }
            } 
          	else if (maxX > minY) {
                // Adjust the partition indexes
                right = partitionX - 1;
            } 
          	else {
                left = partitionX + 1;
            }
        }

        return 0.0;  // Return 0.0 if no median found
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 3, 7, 8};
        int[] nums2 = {2, 4, 6};
        double median = findMedianSortedArrays(nums1, nums2);
        System.out.println("Median: " + median);
    }
}

Output:

Median: 4.0

The time complexity of this logarithmic approach is O(log(min(n, k))), where n and k are the sizes of the two arrays. Since we are dividing the search space in half at each step, the algorithm converges to the median in logarithmic time.

The space complexity of this algorithm is O(1), as it only requires a constant amount of extra space to store the variables.

Analysis of Both Approaches

Let’s see a quick review of all the approaches.

Approach	Time Complexity	Space Complexity	Details
Naive Approach	O(n+k)	O(n+k)	It involves merging the two sorted arrays into a single array and finding the median of the merged array.
Divide and Conquer Approach	O(log(n+k))	O(1)	This approach involves dividing the arrays into two parts and comparing the medians of both arrays based on divide and conquer strategy.

Conclusion

In this article, we learned how to find the median of a sorted array. By leveraging the divide and conquer strategy, we were able to efficiently narrow down the search space and find it in O(log(n+k)) time. Solving this problem efficiently is not only a demonstration of algorithmic processes but also has practical applications in various domains, including data analysis, numerical computing, and more.