Problem: Median of Array
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)).
Input: A : [1 4 5] B : [2 3]
Note: 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
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.
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)
Code in C++