Median in a 2d matrix

#1

im having a question from interview bit on binary search :-
https://www.interviewbit.com/problems/median-of-array/.

can anyone will explain this problem solution step by step
with code.
plz, help me im very confused .

#2

someone please, reply to me please.

#3

please reply to me i have asked this doubt 15-20 mins ago and no one is replying

#4

wait i am reading the problem now

sorry your doubt was missed by me

#5

in this question you have to use the logic of merging two sorted arrays
and while merging make a count also

now if total no of elements are even then
x= (m+n)/2;
y=x-1;
x and y are index
median is avg of xth element and yth element of merged array

now if total no of elements are odd then
median is (m+n)/2 th element of merged array

first try to solve this question using this hint
meanwhile i will provide you the code as well

#6

the time complexity of previous approach is O(n+m)
which will give TLE

Efficient Approach:
The idea is simple, calculate the median of both the arrays and discard one half of each array.

Let’s take an example to understand this
Input :
arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
brr[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19 }

Recursive call 1:
smaller array[] = 1 2 3 4 5 6 7 8 9 10, mid = 5
larger array[] = 11 12 13 14 15 16 17 18 19 , mid = 15

5 < 15
Discard first half of the first array and second half of the second array

Recursive call 2:
smaller array[] = 11 12 13 14 15, mid = 13
larger array[] = 5 6 7 8 9 10, mid = 7

7 < 13
Discard first half of the second array and second half of the first array

Recursive call 3:
smaller array[] = 11 12 13 , mid = 12
larger array[] = 7 8 9 10 , mid = 8

8 < 12
Discard first half of the second array and second half of the first array

Recursive call 4:
smaller array[] = 11 12
larger array[] = 8 9 10

Now, there are some basic corner cases(Base Case)

  1. If the size of smaller array is 0. Return the median of a larger array.
  2. if the size of smaller array is 1.
    1. The size of the larger array is also 1. Return the median of two elements.
    2. If the size of the larger array is odd. Then after adding the element from 2nd array, it will be even so the median will be an average of two mid elements. So the element from the smaller array will affect the median if and only if it lies between (m/2 – 1)th and (m/2 + 1)th element of the larger array. So, find the median in between the four elements, the element of the smaller array and (m/2)th, (m/2 – 1)th and (m/2 + 1)th element of a larger array
    3. Similarly, if the size is even, then check for the median of three elements, the element of the smaller array and (m/2)th, (m/2 – 1)th element of a larger array
  3. If the size of smaller array is 2
    1. If the larger array also has two elements, find the median of four elements.
    2. If the larger array has an odd number of elements, then the median will be one of the following 3 elements
      1. Middle element of larger array
      2. Max of the first element of smaller array and element just before the middle, i.e M/2-1th element in a bigger array
      3. Min of the second element of smaller array and element
        just after the middle in the bigger array, i.e M/2 + 1th element in the bigger array
    3. If the larger array has even number of elements, then the median will be one of the following 4 elements
      1. The middle two elements of the larger array
      2. Max of the first element of smaller array and element just before the first middle element in the bigger array, i.e M/2 – 2nd element
      3. Min of the second element of smaller array and element just after the second middle in the bigger array, M/2 + 1th element