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

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

## Comments