Median of two sorted arrays

There is a coding problem to find the median of two sorted arrays

This can be easily solved by merging those two sorted arrays, then taking the median from the array. This solution using merging takes the time complexity of O(m+n). But this problem is not designed to be implemented in this way.

It is specifically tailored for performing a binary search across two sorted arrays. It’s an extension of the binary search on a single sorted array, so a solid understanding of binary search on a single array is crucial.

In a binary search, we typically partition the sorted array into a left and right subarrays. The index range for the left subarray is [left… mid], while the right subarray is [mid+1 …. right]. If the target value doesn’t match the mid value, and if the target value is greater than the mid value, we search in the right subarray; otherwise, we search in the left subarray.

This same principle can be applied across two sorted arrays. The median is the middle element in the case of an odd-sized array, and the average of the two middle elements in the case of an even-sized array. So this median can be part of array1/array2. When using Binary search concept, we divide array into two subarrays and continue searching. Similar concept applies here. Here are some steps to perform a binary search among two sorted arrays and find the median:

• Partition array1 and array2. part_1_1 starts with the first half of array1, part_2_1 with the first half of array2.
• Here we consider 4 middle elements. Max value of Left subarray1 (MaxLeft1), Min value of right subarray1(MinRight1), Max value of left subarray2 (MaxLeft2) and Min value of right subarray2 (MinRight2).
• If these 4 elements are in the order that is:
  MaxLeft1 <= MinRight2 and MaxLeft2 <= MinRight1
  If this condition is satisfied, the median can be calculated using the following steps:

— If the total number of elements is even numbered:
Get the max left value(MaxLeft) = max(MaxLeft1, MaxLeft2)
Get the min right value(MinRight) = min(MinRight1, MinRight2)
result = (MaxLeft + MinRight)/2
else
result = max(MaxLeft1, MaxLeft2)
— else, this is the case where we need to search for the median in other parts of arrays. There are two cases here:
if MaxLeft1 > MinRight2 that is left sub array1 elements values are greater than array2
so reduce the left sub array1 size and continue searching
note when reducing left subarray1, more number of elements are taken from array2
right_index = part_1_1 -1
else // left sub array elements values are smaller
left_index = part_1_1 + 1 // search in right sub array1

• In the next iteration part_1_1, part_2_1 calculated with the new left and right indices.

This figure shows an example and corresponding initial values

Here’s the C++ solution: