Make delicious recipes!

Find median of 2 sorted arrays if they were merged



Solution: A bianry algorithm for this is as follows:

  1. Compare the medians of the 2 arrays.

  2. If they are equal, median is found.

  3. Else if arr1[mid] < arr2[mid], then:
    1. Eliminate the smaller half of arr1 and
    2. Eliminate the greater half of arr2 as they will form the first quarter and last quarter of the merged arrays.

  4. Recurse for the remaining halves of each array to get the median of the merged arrays.


The above algorithm works well till we get the array sizes down to 2
When any of the arrays' size becomes less than 2, then special cases arise.
Let A[N] and B[M] be the arrays with sizes N and M such that N < M
There are 4 cases:
  1. N=1 and M=even: Median is median of 3 numbers: A[0], B[M/2 - 1] and B[M/2]

  2. N=1 and M=odd: Median is median of 4 numbers: A[0], B[M/2 - 1], B[M/2] and B[M/2 + 1]

  3. N=2 and M=odd: Median is median of 3 numbers: B[M/2], max(A[0], B[M/2 - 1]), min(A[1], B[M/2 + 1])

  4. N=2 and M=even: Median is median of 4 numbers: B[M/2], B[M/2 - 1], max(A[0], B[M/2 - 2]), min(A[1], B[M/2 + 1])






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal