How to Find the Median of Two Sorted Arrays?

Finding the median of two sorted arrays is a common question in technical interviews. It tests both your understanding of algorithms and your coding skills. The median represents the middle value of a sorted list. If the list is of even length, the median is the average of the two middle numbers. When working with two sorted arrays, things can get a bit tricky.

To solve this problem efficiently, we can leverage the properties of the arrays being sorted. The goal is to find the median without merging the two arrays fully, which would take O(n + m) time, where n and m are the sizes of the two arrays. Instead, we can achieve it in O(log(min(n, m))) time using a binary search approach.

Approach

1. Ensure the First Array is Smaller: Start by making sure that array A is the smaller array. If it is not, swap the arrays. This helps simplify our calculations.

2. Binary Search on the Smaller Array: Use binary search to partition both arrays into left and right halves. This means we will determine a partition index for array A (let's call it i) and calculate the corresponding partition index for array B (let's call it j), where j = (n + m + 1) / 2 - i.

3. Check Partition Conditions: After calculating i and j, you check if the partition is valid by ensuring:

   • The largest element on the left side of A is less than or equal to the smallest element on the right side of B.
   • The largest element on the left side of B is less than or equal to the smallest element on the right side of A.

4. Calculate the Median: If the partitions are valid, you can compute the median based on the sizes of the combined arrays, handling both odd and even lengths properly.

Code Example

Here's a Python function that implements this approach:

PythonCopy code

Explanation

The function starts by ensuring that nums1 is the smaller array. It performs binary search on this smaller array to find a suitable partition. If the partitions meet the criteria, it calculates the median, taking into account whether the combined length of the arrays is odd or even.