How to find median of two sorted arrays?

A Quick Overview

Are you struggling to find the median of two sorted arrays? Look no further! With the use of sorting, this problem can be solved efficiently.

Median is defined as the middle element in a sorted array. If the array has even number of elements, it is the average of the two middle elements.

What is Median?

Given the two sorted arrays A and B of sizes m and n respectively, we have to find the median of the two sorted arrays.

Problem Statement

Example: Input:  A[] = {1, 4, 5}, B[] = {2, 3}  Output: 3  Explanation: Merging both the arrays and arranging them in ascending: [1, 2, 3, 4, 5] Hence, the median is 3

Merge both sorted arrays A and B into a new auxiliary array & find the median, either by selecting middle element in an odd-length array or taking the mean of the two middle elements in an even-length array.

Simple Approach: Using Extra Space

Time complexity: O(N + M) where N and M is size of the array A[] & B[] Space complexity: O(1)

Since both arrays are sorted, a binary search approach can be employed. The binary search allows us to eliminate parts of the arrays that do not contribute to the answer.

Efficient Approach (Using binary search)

Time complexity: O(log(min(N,M)) where N and M is size of the array A[] & B[]. Space complexity: O(1)

Want to explore these approaches and learn how to implement these in various programming languages?

Click on the link below to start your journey.