top of page

### Looking to master object-oriented and system design for tech interviews or career growth?

• Improve your system design and machine coding skills.

• Study with our helpful resources.

**We're in beta mode and would love to hear your feedback.

Search

# 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)

Code in C++

Tags:

bottom of page