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, 2022 in Others by krishna
• 2,820 points
341 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

Getting a union of two arrays in JavaScript

Say I have two arrays: one with ...READ MORE

Aug 18, 2022 in Others by krishna
• 2,820 points
256 views
0 votes
0 answers

How to merge two sorted arrays into a sorted array?

this question was asked in interview  public static ...READ MORE

Nov 17, 2022 in Others by Ashwini
• 5,430 points
330 views
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

Aug 8, 2022 in Others by krishna
• 2,820 points
326 views
0 votes
0 answers

Combine two arrays

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

Aug 8, 2022 in Others by krishna
• 2,820 points
444 views
0 votes
1 answer

Excel: Median of even number of values with a condition

The LARGE function, COUNT function, and TRUNC ...READ MORE

answered Nov 26, 2022 in Others by narikkadan
• 63,420 points
438 views
0 votes
1 answer

Count the sum of difference between two cells

Use a for loop: Sub AbsoluteDifference() ...READ MORE

answered Jan 15, 2023 in Others by narikkadan
• 63,420 points
206 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
3,515 views
+2 votes
1 answer
webinar REGISTER FOR FREE WEBINAR X
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP