__Median of two sorted arrays of different sizes__

__Median of two sorted arrays of different sizes__

** Problem statement ** : We are given two arrays of integers of different sizes
and they are in sorted order, and we need to find the median element if we
combine these two arrays.

**Input: **
**int**
** **
**ar1[] = {50}; **

**int**
** **
**ar2[] = {1, 3, 5, 10}; **

** **

**
Output:
5
Explanation: as after sorting the array, we have {1, 3, 5, 10, 50}
hence median of this array 5
**

**Naïve approach: ** If we merge these two arrays like we merge in merge sort
algorithm, then finding the middle element, it will take linear time, O(n).
This doesn’t look good because we are not using the property that median
lies always at the middle when elements are sorted.

** Efficient approach: ** As we know median of a sorted array lies at its centre,
we now need to use this property here. Let’s assume the array with smaller
number of elements to be A and second one to be B.

Now take the mid of these arrays, if the mid of A is less than or equal to mid value of B then we can observe that median will lie before the mid of B and after the mid of A or else vice versa.

** Proof of above statement: ** Suppose we have only one sorted array and its
median is middle element, now if we insert some elements in it which are
greater than its median then obviously median will shift towards right, so
we can now think above statement as analogous to this and observe that we
can actually leave half parts of both, we can perform this recursively.

There will be some corner cases, when size of small array becomes 2 or 1 then we have to solve answer manually, we will see more clearly in our code.

**Implementation in C++:**

**Time Complexity: O(logn) **

It is highly recommended to solve below problems, they are handpicked by Programmers Army:

__Practice Problems :-__

• https://leetcode.com/problems/median-of-two-sorted-arrays/

This article is contributed by Sanchit Kumavat

So that’s it for this article we will be coming up with our next article on further topics of Algorithms very soon till then keep learning, keep coding, keep reading and keep improving !!

**Happy Coding **

**By Programmers Army **
**😊**