Median Of Two Sorted Arrays In C++ Program

Finding the median of two sorted arrays is a common problem in computer science that tests understanding of arrays, sorting, and efficient algorithms.

In this article, you will learn how to approach this problem using different C++ programming techniques, from a straightforward merging method to an optimized binary search approach.

Problem Statement

The challenge is to determine the median value from two input arrays, nums1 and nums2, both of which are already sorted in ascending order. The median is the middle element of a sorted list. If the list has an odd number of elements, the median is the single middle element. If it has an even number of elements, the median is the average of the two middle elements. The goal is to solve this efficiently, ideally with a time complexity of O(log(m+n)), where 'm' and 'n' are the lengths of the two arrays. This problem often arises in data analysis and competitive programming scenarios where efficient merging and statistical calculations are critical.

Example

Let's consider two sorted arrays: nums1 = [1, 3] nums2 = [2]

If these arrays were combined and sorted, the result would be [1, 2, 3]. The median of this combined list is 2.

Another example: nums1 = [1, 2] nums2 = [3, 4]

Combined and sorted: [1, 2, 3, 4]. The median is the average of the two middle elements (2 and 3), which is (2 + 3) / 2 = 2.5.

Background & Knowledge Prerequisites

To effectively understand and implement the solutions, readers should be familiar with:

• C++ Basics: Fundamental syntax, data types, loops, and conditional statements.
• Arrays/Vectors: How to declare, initialize, and manipulate std::vector in C++.
• Sorting Concepts: Understanding what sorted arrays mean and how they behave.
• Median Definition: The statistical concept of a median for both odd and even sized datasets.
• Time and Space Complexity: Basic understanding of Big O notation to evaluate algorithm efficiency.

 

Relevant imports and setup information for C++ solutions typically involve including , , and .

Use Cases or Case Studies

Finding the median of sorted arrays has several practical applications:

• Database Query Optimization: When merging sorted result sets from different tables or partitions, quickly finding the median can be part of aggregation queries or for sampling purposes.
• Statistical Analysis: In various fields like finance or biology, data often comes in sorted streams. Calculating the median of combined datasets is a fundamental step for robust statistical analysis, as the median is less sensitive to outliers than the mean.
• Online Judge Problems/Competitive Programming: This problem is a classic for testing algorithmic thinking, particularly for efficient merging or binary search techniques, and frequently appears on platforms like LeetCode or HackerRank.
• Real-time Data Processing: In systems that process large streams of sorted sensor data or log entries, efficiently computing the median of a combined window can be crucial for anomaly detection or system health monitoring.
• Resource Allocation: In scenarios where resources (e.g., network bandwidth, CPU time) are allocated based on sorted priority queues, determining the "middle" priority can help in fair distribution strategies.

 

Solution Approaches

We will explore two distinct approaches to solve this problem: one straightforward method involving merging the arrays, and a more optimized method using binary search.

Approach 1: Merge and Find Median

This approach involves merging the two sorted arrays into a single, larger sorted array. Once merged, finding the median is a simple matter of accessing elements based on the combined array's length.

• Summary: Combine nums1 and nums2 into a single sorted array, then calculate the median from this merged array.

 

// Median of Two Sorted Arrays (Merge Approach)
#include <iostream>
#include <vector>
#include <algorithm> // For std::sort (though not strictly needed if merging carefully)

using namespace std;

double findMedianSortedArraysMerge(const vector<int>& nums1, const vector<int>& nums2) {
    // Step 1: Create a new vector to store merged elements
    vector<int> merged;
    merged.reserve(nums1.size() + nums2.size()); // Pre-allocate memory for efficiency

    // Step 2: Merge elements from nums1 and nums2 into 'merged'
    // This can be done efficiently because both input arrays are already sorted.
    // Use two pointers, one for each input array.
    int i = 0, j = 0;
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] < nums2[j]) {
            merged.push_back(nums1[i]);
            i++;
        } else {
            merged.push_back(nums2[j]);
            j++;
        }
    }

    // Step 3: Add remaining elements from nums1 (if any)
    while (i < nums1.size()) {
        merged.push_back(nums1[i]);
        i++;
    }

    // Step 4: Add remaining elements from nums2 (if any)
    while (j < nums2.size()) {
        merged.push_back(nums2[j]);
        j++;
    }

    // Step 5: Calculate the median
    int total_size = merged.size();
    if (total_size % 2 == 1) { // Odd number of elements
        return merged[total_size / 2];
    } else { // Even number of elements
        // Median is the average of the two middle elements
        return (merged[total_size / 2 - 1] + merged[total_size / 2]) / 2.0;
    }
}

int main() {
    // Example 1:
    vector<int> nums1_ex1 = {1, 3};
    vector<int> nums2_ex1 = {2};
    cout << "Example 1 (Merge): nums1 = {1, 3}, nums2 = {2}" << endl;
    cout << "Median: " << findMedianSortedArraysMerge(nums1_ex1, nums2_ex1) << endl; // Expected: 2.0

    // Example 2:
    vector<int> nums1_ex2 = {1, 2};
    vector<int> nums2_ex2 = {3, 4};
    cout << "Example 2 (Merge): nums1 = {1, 2}, nums2 = {3, 4}" << endl;
    cout << "Median: " << findMedianSortedArraysMerge(nums1_ex2, nums2_ex2) << endl; // Expected: 2.5

    // Example 3: Empty arrays
    vector<int> nums1_ex3 = {};
    vector<int> nums2_ex3 = {1, 2, 3, 4, 5};
    cout << "Example 3 (Merge): nums1 = {}, nums2 = {1, 2, 3, 4, 5}" << endl;
    cout << "Median: " << findMedianSortedArraysMerge(nums1_ex3, nums2_ex3) << endl; // Expected: 3.0

    return 0;
}

Run

• Sample Output:

Example 1 (Merge): nums1 = {1, 3}, nums2 = {2}
Median: 2
Example 2 (Merge): nums1 = {1, 2}, nums2 = {3, 4}
Median: 2.5
Example 3 (Merge): nums1 = {}, nums2 = {1, 2, 3, 4, 5}
Median: 3

 

• Stepwise Explanation:

1. A new std::vector called merged is created to hold all elements from both input arrays.
2. Two pointers, i for nums1 and j for nums2, are initialized to 0.
3. Elements are iteratively picked from nums1 or nums2 and added to merged. The smaller element at the current pointer positions is always chosen, ensuring merged remains sorted.
4. After one array is exhausted, the remaining elements of the other array are simply appended to merged.
5. Once merged contains all elements, its total size is checked.
6. If the total size is odd, the median is the element at merged[total_size / 2].
7. If the total size is even, the median is the average of merged[total_size / 2 - 1] and merged[total_size / 2].
8. The time complexity for this approach is O(m+n) due to merging all elements, and space complexity is also O(m+n) for the merged array.

Approach 2: Binary Search (Optimized)

This approach aims to find the "partition point" in the two arrays such that all elements to the left of the partition are less than or equal to all elements to the right. This can be achieved using binary search without actually merging the arrays. The key idea is to ensure that when we divide the combined elements into two halves, the maximum element of the left half is less than or equal to the minimum element of the right half.

• Summary: Use binary search on the smaller array to find an optimal partition that divides the combined elements into two equal halves, satisfying the median property (left max <= right min).

 

// Median of Two Sorted Arrays (Binary Search Approach)
#include <iostream>
#include <vector>
#include <algorithm> // For std::max, std::min
#include <climits>   // For INT_MIN, INT_MAX

using namespace std;

double findMedianSortedArraysBinarySearch(const vector<int>& nums1, const vector<int>& nums2) {
    // Step 1: Ensure nums1 is the smaller array to optimize binary search range
    if (nums1.size() > nums2.size()) {
        return findMedianSortedArraysBinarySearch(nums2, nums1);
    }

    int m = nums1.size();
    int n = nums2.size();
    int low = 0;
    int high = m; // Binary search range for the partition in nums1

    // Step 2: Perform binary search to find the correct partition
    while (low <= high) {
        int partitionX = low + (high - low) / 2; // Partition point in nums1
        // partitionY determines the partition point in nums2
        // total elements in left_half = (m + n + 1) / 2
        // elements from nums1 in left_half = partitionX
        // elements from nums2 in left_half = ((m + n + 1) / 2) - partitionX
        int partitionY = (m + n + 1) / 2 - partitionX;

        // Step 3: Determine elements around the partitions
        // L1: Max element on the left side of partitionX in nums1
        // R1: Min element on the right side of partitionX in nums1
        // L2: Max element on the left side of partitionY in nums2
        // R2: Min element on the right side of partitionY in nums2

        // Handle edge cases where partitionX or partitionY is at the beginning (0) or end (m or n)
        int L1 = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
        int R1 = (partitionX == m) ? INT_MAX : nums1[partitionX];

        int L2 = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
        int R2 = (partitionY == n) ? INT_MAX : nums2[partitionY];

        // Step 4: Check if the partition is correct
        if (L1 <= R2 && L2 <= R1) {
            // Found the correct partition
            // The combined array is effectively partitioned into two halves
            // Left Half: elements up to L1 and L2
            // Right Half: elements from R1 and R2 onwards

            if ((m + n) % 2 == 1) { // Odd total number of elements
                // Median is the maximum of the left half's boundary elements
                return max(L1, L2);
            } else { // Even total number of elements
                // Median is the average of the two middle elements
                // The two middle elements are max(L1, L2) and min(R1, R2)
                return (max(L1, L2) + min(R1, R2)) / 2.0;
            }
        } else if (L1 > R2) {
            // L1 is too large, meaning partitionX is too far to the right.
            // Move partitionX to the left in nums1.
            high = partitionX - 1;
        } else { // L2 > R1
            // L2 is too large, meaning partitionX is too far to the left.
            // Move partitionX to the right in nums1.
            low = partitionX + 1;
        }
    }
    // Should not reach here if inputs are sorted arrays as specified.
    return 0.0;
}

int main() {
    // Example 1:
    vector<int> nums1_ex1 = {1, 3};
    vector<int> nums2_ex1 = {2};
    cout << "Example 1 (Binary Search): nums1 = {1, 3}, nums2 = {2}" << endl;
    cout << "Median: " << findMedianSortedArraysBinarySearch(nums1_ex1, nums2_ex1) << endl; // Expected: 2.0

    // Example 2:
    vector<int> nums1_ex2 = {1, 2};
    vector<int> nums2_ex2 = {3, 4};
    cout << "Example 2 (Binary Search): nums1 = {1, 2}, nums2 = {3, 4}" << endl;
    cout << "Median: " << findMedianSortedArraysBinarySearch(nums1_ex2, nums2_ex2) << endl; // Expected: 2.5

    // Example 3: Empty array, other array has elements
    vector<int> nums1_ex3 = {};
    vector<int> nums2_ex3 = {1, 2, 3, 4, 5};
    cout << "Example 3 (Binary Search): nums1 = {}, nums2 = {1, 2, 3, 4, 5}" << endl;
    cout << "Median: " << findMedianSortedArraysBinarySearch(nums1_ex3, nums2_ex3) << endl; // Expected: 3.0

    // Example 4: Mixed lengths
    vector<int> nums1_ex4 = {1, 3, 5, 7, 9};
    vector<int> nums2_ex4 = {2, 4, 6, 8, 10};
    cout << "Example 4 (Binary Search): nums1 = {1,3,5,7,9}, nums2 = {2,4,6,8,10}" << endl;
    cout << "Median: " << findMedianSortedArraysBinarySearch(nums1_ex4, nums2_ex4) << endl; // Expected: 5.5 (elements: 1-10, median: (5+6)/2)

    // Example 5: Another test
    vector<int> nums1_ex5 = {4, 5, 6, 8, 9};
    vector<int> nums2_ex5 = {1, 2, 3, 7, 10};
    cout << "Example 5 (Binary Search): nums1 = {4,5,6,8,9}, nums2 = {1,2,3,7,10}" << endl;
    cout << "Median: " << findMedianSortedArraysBinarySearch(nums1_ex5, nums2_ex5) << endl; // Expected: 5.5 (elements: 1,2,3,4,5,6,7,8,9,10)


    return 0;
}

Run

• Sample Output:

Example 1 (Binary Search): nums1 = {1, 3}, nums2 = {2}
Median: 2
Example 2 (Binary Search): nums1 = {1, 2}, nums2 = {3, 4}
Median: 2.5
Example 3 (Binary Search): nums1 = {}, nums2 = {1, 2, 3, 4, 5}
Median: 3
Example 4 (Binary Search): nums1 = {1,3,5,7,9}, nums2 = {2,4,6,8,10}
Median: 5.5
Example 5 (Binary Search): nums1 = {4,5,6,8,9}, nums2 = {1,2,3,7,10}
Median: 5.5

 

• Stepwise Explanation:

1. Preprocessing: The function first ensures that nums1 is always the smaller array. This helps in defining the binary search range more efficiently (searching on the smaller array).
2. Binary Search Setup: low and high define the search space for partitionX, which is the cut point in nums1. partitionX indicates how many elements from nums1 are included in the "left half" of the combined, implicitly sorted array.
3. Calculate partitionY: Based on partitionX, partitionY (the cut point in nums2) is calculated such that the total number of elements in the left halves (partitionX + partitionY) is (m + n + 1) / 2. The +1 ensures that if (m+n) is odd, the left half has one more element, making max(L1, L2) the direct median.
4. Define L1, R1, L2, R2: These four variables represent the elements just before (L) and just after (R) the partition points in both arrays. INT_MIN and INT_MAX are used for edge cases where a partition is at the beginning or end of an array to avoid out-of-bounds access and correctly evaluate comparisons.
5. Check Partition Validity:
   • The core condition for a valid partition is L1 <= R2 and L2 <= R1. This means the largest element in the left half of the combined "array" is less than or equal to the smallest element in the right half.

• If valid, the median is calculated:
• For an odd total count (m+n), the median is max(L1, L2).
• For an even total count (m+n), the median is (max(L1, L2) + min(R1, R2)) / 2.0.
• If L1 > R2, it means partitionX is too large (we've taken too many elements from nums1 into the left half). The high pointer is moved to partitionX - 1 to search in the left half of nums1.
• If L2 > R1, it means partitionX is too small (we need more elements from nums1 or fewer from nums2 in the left half). The low pointer is moved to partitionX + 1 to search in the right half of nums1.

1. The time complexity for this binary search approach is O(log(min(m, n))) because the search space is effectively halved in each iteration of the binary search, and the search is performed on the smaller array. The space complexity is O(1) as no additional arrays are used.

Conclusion

Finding the median of two sorted arrays is a problem that highlights the power of algorithmic optimization. The straightforward merge-and-find approach is easy to understand and implement, offering a time complexity of O(m+n) and space complexity of O(m+n). However, for larger datasets, the binary search approach provides a significantly more efficient solution with a time complexity of O(log(min(m, n))) and constant space complexity O(1). Choosing the right approach depends on the constraints of the problem, particularly the size of the input arrays and performance requirements. The binary search method, while more complex to grasp initially, is the preferred solution for its optimal efficiency.

Summary

• Problem: Calculate the median of two given sorted arrays.
• Median Definition: Middle element for odd length, average of two middle for even length.
• Approach 1: Merge and Find:
• Method: Combine both arrays into a single sorted array.
• Median Calculation: Index based on the merged array's total length.
• Complexity: Time O(m+n), Space O(m+n).
• Approach 2: Binary Search (Optimized):
• Method: Find an optimal partition in the smaller array using binary search.
• Condition: Ensure max(left_elements) <= min(right_elements).
• Median Calculation: Derived from the boundary elements of the correct partition.
• Complexity: Time O(log(min(m, n))), Space O(1).
• Best Practice: The binary search approach is generally preferred for its superior time complexity, making it suitable for large inputs.