Median of Array InterviewBit Solution

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: 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

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:

1. if A[m1] < B[m2 - 1], that means the current index is too small, to be at mid.

2. if B[m2] < A[m1 - 1], that means the current index is too large, to be at mid.

3. 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++