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 😊