Median of two sorted arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log(min(m,n))).

Input-Output Examples

Example 1:

Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
Explanation: merged array = [1, 2, 3] and median is 2.0

Example 2:

Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5
Explanation: merged array = [1, 2, 3, 4] and median is (2 + 3) / 2 = 2.5

Approach: Binary Search

  1. Ensure the First Array is Smaller: We always want to binary search on the smaller array to maintain O(log(min(m,n))) complexity.
  2. Binary Search:
    • Partition both arrays at positions i and j such that the total number of elements in the left partition equals the total number of elements in the right partition.
    • Adjust i and j to satisfy the condition: max(left_part1) <= min(right_part2) and max(left_part2) <= min(right_part1).
  3. Find Median:
    • If the combined length is odd, the median is the maximum of the left parts.
    • If the combined length is even, the median is the average of the maximum of the left parts and the minimum of the right parts.

C++ Program to find the median of two sorted arrays

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to find the median of two sorted arrays
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();
    
    // Ensure nums1 is the smaller array
    if (m > n) {
        return findMedianSortedArrays(nums2, nums1);
    }
    
    int imin = 0, imax = m, half_len = (m + n + 1) / 2;
    
    while (imin <= imax) {
        int i = (imin + imax) / 2; // Partition nums1
        int j = half_len - i; // Partition nums2
        
        // i is too small, must increase it
        if (i < m && nums1[i] < nums2[j - 1]) {
            imin = i + 1;
        }
        // i is too big, must decrease it
        else if (i > 0 && nums1[i - 1] > nums2[j]) {
            imax = i - 1;
        }
        // i is perfect
        else {
            int max_of_left;
            if (i == 0) {
                max_of_left = nums2[j - 1];
            } else if (j == 0) {
                max_of_left = nums1[i - 1];
            } else {
                max_of_left = max(nums1[i - 1], nums2[j - 1]);
            }
            if ((m + n) % 2 == 1) { // If the total number of elements is odd
                return max_of_left;
            }
            
            int min_of_right;
            if (i == m) {
                min_of_right = nums2[j];
            } else if (j == n) {
                min_of_right = nums1[i];
            } else {
                min_of_right = min(nums1[i], nums2[j]);
            }
            
            return (max_of_left + min_of_right) / 2.0; // If the total number of elements is even
        }
    }
    return 0.0; // Edge case
}

int main() {
    vector<int> nums1 = {1, 3};
    vector<int> nums2 = {2};
    double median = findMedianSortedArrays(nums1, nums2);
    cout << "Median of the two sorted arrays: " << median << endl;
    return 0;
}

Java Program to find the median of two sorted arrays

java
public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        double median = findMedianSortedArrays(nums1, nums2);
        System.out.println("Median of the two sorted arrays: " + median);
    }

    // Function to find the median of two sorted arrays
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        
        // Ensure nums1 is the smaller array
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int imin = 0, imax = m, half_len = (m + n + 1) / 2;
        
        while (imin <= imax) {
            int i = (imin + imax) / 2; // Partition nums1
            int j = half_len - i; // Partition nums2
            
            // i is too small, must increase it
            if (i < m && nums1[i] < nums2[j - 1]) {
                imin = i + 1;
            }
            // i is too big, must decrease it
            else if (i > 0 && nums1[i - 1] > nums2[j]) {
                imax = i - 1;
            }
            // i is perfect
            else {
                int max_of_left;
                if (i == 0) {
                    max_of_left = nums2[j - 1];
                } else if (j == 0) {
                    max_of_left = nums1[i - 1];
                } else {
                    max_of_left = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) { // If the total number of elements is odd
                    return max_of_left;
                }
                
                int min_of_right;
                if (i == m) {
                    min_of_right = nums2[j];
                } else if (j == n) {
                    min_of_right = nums1[i];
                } else {
                    min_of_right = Math.min(nums1[i], nums2[j]);
                }
                
                return (max_of_left + min_of_right) / 2.0; // If the total number of elements is even
            }
        }
        return 0.0; // Edge case
    }
}

Python Program to find the median of two sorted arrays

python
def findMedianSortedArrays(nums1, nums2):
    m, n = len(nums1), len(nums2)
    
    # Ensure nums1 is the smaller array
    if m > n:
        nums1, nums2, m, n = nums2, nums1, n, m
    
    imin, imax, half_len = 0, m, (m + n + 1) // 2
    
    while imin <= imax:
        i = (imin + imax) // 2 # Partition nums1
        j = half_len - i # Partition nums2
        
        # i is too small, must increase it
        if i < m and nums1[i] < nums2[j - 1]:
            imin = i + 1
        # i is too big, must decrease it
        elif i > 0 and nums1[i - 1] > nums2[j]:
            imax = i - 1
        # i is perfect
        else:
            if i == 0:
                max_of_left = nums2[j - 1]
            elif j == 0:
                max_of_left = nums1[i - 1]
            else:
                max_of_left = max(nums1[i - 1], nums2[j - 1])
            if (m + n) % 2 == 1: # If the total number of elements is odd
                return max_of_left

            if i == m:
                min_of_right = nums2[j]
            elif j == n:
                min_of_right = nums1[i]
            else:
                min_of_right = min(nums1[i], nums2[j])

            return (max_of_left + min_of_right) / 2.0 # If the total number of elements is even
    
    return 0.0 # Edge case

if __name__ == "__main__":
    nums1 = [1, 3]
    nums2 = [2]
    median = findMedianSortedArrays(nums1, nums2)
    print(f"Median of the two sorted arrays: {median}")

DSA

4408

714

Related Articles