Median of Array InterviewBit Solution
Updated: Sep 11, 2020
Problem: Median of Array
Problem Description:
There are two sorted arrays A and B of size m and n respectively.
Find the median of the two sorted arrays ( The median of the array formed by merging both the arrays ).
The overall run time complexity should be O(log (m+n)).
Sample Input
Input:
A : [1 4 5]
B : [2 3] Sample Output
Output: 3Note: IF the number of elements in the merged array is even, then the median is the average of (n / 2)th and (n/2 + 1)th element.
For example, if the array is [1 2 3 4], the median is (2 + 3) / 2.0 = 2.5
Approach:
Let us have two arrays A and B with size n1 and n2 respectively. So if we combine these two arrays we would get an array of size (n1 + n2).
To find median of this array we would have to go for ((n1 + n2) / 2)th element.
So let, half = (n1 + n2)/2;
And do binary search on any one array, in our case we have taken the array with the minimum size, we would call it A here.So in our binary search, suppose m1 is the current index of our array A. Then if we are interested in ((n1 + n2) / 2)th i.e. half, then m2 (current index of array B) would be equal to half - m1.
As we need, m1 + m2 = half Now, we have three conditions:
if A[m1] < B[m2 - 1], that means the current index is too small, to be at mid.
if B[m2] < A[m1 - 1], that means the current index is too large, to be at mid.
Otherwise, we found our cut.
Reason:
Condition 1: A[m1] < B[m2 - 1],
- That means there might exist some indexes greater than m1, that are smaller than B[m2 - 1]. That's why we have to move the current index towards right. Because when we move m1 to the right, m2 would shift towards left.Condition 2: B[m2] < A[m1 - 1],
- That means there might exist some indexes greater than m2, that are smaller than A[m1 - 1]. That's why we have to move the current index towards left. Because when we move m1 to the left, m2 would shift towards right.Condition 3: When we found our cut.
- So now we have to check whether (n1 + n2) is odd or not, if it is odd, then return the max value from the left side.
- If it is not odd, then we have to find min value from the right side as well. And then return (maxLeft + minRight)/2.Time & Space Complexity:
Time Complexity: O(log(min(n,m))) - where n & m are the size of two arrays.
Space Complexity: O(1) - as we have not taken extra space (Ignoring space taken by the given arrays)
Solution:
Code in C++



Doing the binary search on the smaller array is the detail that actually makes this approach click for me, since it keeps the partition logic from getting tangled when the array sizes are lopsided. I kept second-guessing myself on the maxLeft and minRight boundaries when a partition lands at index 0, and comparing implementations on https://zonderregistratie.com helped me see how that edge case plays out differently. Tracing the sample by hand made the O(log(min(n,m))) complexity feel far less intimidating than it looks at first glance.