Example: Median of Two Sorted Arrays (Merge Approach)

// Median of Two Sorted Arrays (Merge Approach)
#include <stdio.h>
#include <stdlib.h> // For malloc

// Function to find the median of two sorted arrays by merging
double findMedianSortedArrays_Merge(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    // Step 1: Create a new array to store merged elements
    int totalSize = nums1Size + nums2Size;
    int* merged = (int*)malloc(totalSize * sizeof(int));
    if (merged == NULL) {
        perror("Failed to allocate memory for merged array");
        exit(EXIT_FAILURE);
    }

    // Step 2: Merge nums1 and nums2 into 'merged'
    int i = 0, j = 0, k = 0;
    while (i < nums1Size && j < nums2Size) {
        if (nums1[i] < nums2[j]) {
            merged[k++] = nums1[i++];
        } else {
            merged[k++] = nums2[j++];
        }
    }
    // Copy remaining elements from nums1, if any
    while (i < nums1Size) {
        merged[k++] = nums1[i++];
    }
    // Copy remaining elements from nums2, if any
    while (j < nums2Size) {
        merged[k++] = nums2[j++];
    }

    // Step 3: Calculate the median
    double median;
    if (totalSize % 2 == 1) { // Odd number of elements
        median = (double)merged[totalSize / 2];
    } else { // Even number of elements
        median = (double)(merged[totalSize / 2 - 1] + merged[totalSize / 2]) / 2.0;
    }

    // Step 4: Free allocated memory
    free(merged);
    return median;
}

int main() {
    // Example 1: Odd total number of elements
    int nums1_ex1[] = {1, 3};
    int nums2_ex1[] = {2};
    int nums1Size_ex1 = sizeof(nums1_ex1) / sizeof(nums1_ex1[0]);
    int nums2Size_ex1 = sizeof(nums2_ex1) / sizeof(nums2_ex1[0]);
    double median_ex1 = findMedianSortedArrays_Merge(nums1_ex1, nums1Size_ex1, nums2_ex1, nums2Size_ex1);
    printf("Example 1: nums1 = {1, 3}, nums2 = {2} -> Median: %.1f\n", median_ex1); // Expected: 2.0

    // Example 2: Even total number of elements
    int nums1_ex2[] = {1, 2};
    int nums2_ex2[] = {3, 4};
    int nums1Size_ex2 = sizeof(nums1_ex2) / sizeof(nums1_ex2[0]);
    int nums2Size_ex2 = sizeof(nums2_ex2) / sizeof(nums2_ex2[0]);
    double median_ex2 = findMedianSortedArrays_Merge(nums1_ex2, nums1Size_ex2, nums2_ex2, nums2Size_ex2);
    printf("Example 2: nums1 = {1, 2}, nums2 = {3, 4} -> Median: %.1f\n", median_ex2); // Expected: 2.5

    // Example 3: Different lengths
    int nums1_ex3[] = {0, 0};
    int nums2_ex3[] = {0, 0};
    int nums1Size_ex3 = sizeof(nums1_ex3) / sizeof(nums1_ex3[0]);
    int nums2Size_ex3 = sizeof(nums2_ex3) / sizeof(nums2_ex3[0]);
    double median_ex3 = findMedianSortedArrays_Merge(nums1_ex3, nums1Size_ex3, nums2_ex3, nums2Size_ex3);
    printf("Example 3: nums1 = {0, 0}, nums2 = {0, 0} -> Median: %.1f\n", median_ex3); // Expected: 0.0

    return 0;
}