Median of 2 Sorted Arrays in C ,C++ and Python

[Ikshvaku24]

Is your feature request related to a problem? Please describe. The problem is to implement a function find_median that takes two sorted arrays. This function returns median of the 2 sorted arrays in an efficient way.

Describe the solution you'd like The solution uses modified binary-search by partitioning both arrays such that the number of elements on the left side of the combined array is equal to the number of elements on the right side of the combined array. This approach works in O(min(log M, log N)) time complexity which is the most efficient in time and space complexity. The solution will handle many edge cases including if the partition is in extremes.

Additional context This problem is an important part of binary search as we are maintaining equal number of elements on both sides of combined array while partitioning them. @Kumar-laxmi Please assign me this issue under SSOC'23.

[ayushgupta9906]

Please assign me the issue under SSOC'23

C++

#include <iostream>
#include <vector>
#include <algorithm>

double findMedianSortedArrays(const std::vector<int>& nums1, const std::vector<int>& nums2) {
    std::vector<int> merged;
    merged.reserve(nums1.size() + nums2.size());
    merged.insert(merged.end(), nums1.begin(), nums1.end());
    merged.insert(merged.end(), nums2.begin(), nums2.end());
    
    std::sort(merged.begin(), merged.end());
    
    int n = merged.size();
    if (n % 2 == 0) {
        return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
    } else {
        return merged[n / 2];
    }
}

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

C

#include <stdio.h>

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int mergedSize = nums1Size + nums2Size;
    int merged[mergedSize];
    int i, j, k;
    
    // Merge the two sorted arrays
    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++];
        }
    }
    
    while (i < nums1Size) {
        merged[k++] = nums1[i++];
    }
    
    while (j < nums2Size) {
        merged[k++] = nums2[j++];
    }
    
    // Find the median
    int medianIndex = mergedSize / 2;
    if (mergedSize % 2 == 0) {
        return (merged[medianIndex - 1] + merged[medianIndex]) / 2.0;
    } else {
        return merged[medianIndex];
    }
}

int main() {
    int nums1[] = {1, 3};
    int nums1Size = sizeof(nums1) / sizeof(nums1[0]);
    
    int nums2[] = {2, 4};
    int nums2Size = sizeof(nums2) / sizeof(nums2[0]);
    
    double median = findMedianSortedArrays(nums1, nums1Size, nums2, nums2Size);
    printf("Median: %f\n", median);
    
    return 0;
}

Python

def findMedianSortedArrays(nums1, nums2):
    merged = sorted(nums1 + nums2)
    n = len(merged)
    
    if n % 2 == 0:
        return (merged[n // 2 - 1] + merged[n // 2]) / 2.0
    else:
        return merged[n // 2]

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

[vaishnavi-bhogi19]

please assign this issue to me under ssoc'23

[github-actions[bot]]

This issue has been automatically closed because it has been inactive for many days. Please reopen if you still intend on working on this problem