median of two sorted arrays

0 votes

So I saw this post where the objective is to find out the median of two arrays merged. Note that equal length sorted arrays are being utilized for this as input. Here's the algorithm

Algorithm:

1) Calculate the medians m1 and m2 of the input arrays ar1[] 
   and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
     return m1 (or m2)
3) If m1 is greater than m2, then median is present in one 
   of the below two subarrays.
    a)  From first element of ar1 to m1 (ar1[0...|_n/2_|])
    b)  From m2 to last element of ar2  (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one    
   of the below two subarrays.
   a)  From m1 to last element of ar1  (ar1[|_n/2_|...n-1])
   b)  From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays 
   becomes 2.
6) If size of the two arrays is 2 then use below formula to get 
  the median.
    Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

Example:

   ar1[] = {1, 12, 15, 26, 38}
   ar2[] = {2, 13, 17, 30, 45}

For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

   [15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:

    m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become

  [15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
                       = (max(15, 13) + min(26, 17))/2 
                       = (15 + 17)/2
                       = 16

I can comprehend to some extend that how the excluding of halves work in arrays and the median would be in halves of the arrays like steps 1,2,3,4,5.

However, I can't understand that how they can imply that the median of the merged arrays would automatically be the median of the merged arrays after trimming the two half of arrays. Like the median of merge array of {1,12,15,26,38} and {2,13,17,30,45} would be the median of the merge array of {2,13,17} and {15,26,38}

Can someone explain this to me?

Aug 1 in Others by krishna
• 2,540 points
16 views

No answer to this question. Be the first to respond.

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.

Related Questions In Others

0 votes
0 answers

How can I get the intersection, union, and subset of arrays in Ruby?

I want to develop many methods for ...READ MORE

4 days ago in Others by krishna
• 2,540 points
8 views
0 votes
0 answers

Combine two arrays

I have two arrays structures like this array( ...READ MORE

4 days ago in Others by krishna
• 2,540 points
12 views
0 votes
1 answer

Different types of Collation Sensitivity

Following are the different types of collation ...READ MORE

answered Oct 10, 2018 in Others by CodingByHeart77
• 3,720 points
1,287 views
0 votes
1 answer

Reducing sequences in an array of strings

I've written a C# app to solves ...READ MORE

answered Nov 2, 2018 in Others by DataKing99
• 8,240 points
258 views
0 votes
1 answer
0 votes
2 answers

What are the applications of artificial neural networks?

Artificial neural network is a computational model ...READ MORE

answered Mar 2, 2019 in Others by SA
• 1,050 points
1,114 views
+15 votes
2 answers

Git management technique when there are multiple customers and need multiple customization?

Consider this - In 'extended' Git-Flow, (Git-Multi-Flow, ...READ MORE

answered Mar 27, 2018 in DevOps & Agile by DragonLord999
• 8,450 points
1,770 views
+2 votes
1 answer
webinar REGISTER FOR FREE WEBINAR X
Send OTP
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP