Question

Given two sorted arrays A and B of numbers. The size of A is N and the size of B is n + 1. Say that the numbers in A U B are pairwise distinct (no value returns more than once). Note that A U B has odd size because its 2n + 1. Hence the median is unique. Give an algorithm that returns the median. PSEUDOCODE ONLY.

Answer 1

Pseudocode To find median of a sorted array

1. IF size of array is 1 return array[0]

2. ELSE IF size of array is 2 return (array[0]+array[size-1])/2

3 ELSE

4 IF size is odd return array[mid]

5 ELSEreturn (array[mid] + array[mid+1])/2

6. END

Now we have two sorted arrays arr1 and arr2. To find median of two sorted arrays the best way is to find median m1 and m2 of both arrays and if median of both arrays is same then median is the common number otherwise if m1 < m2 then elements on the right side of in arr2 are compared to elements on right side of m1 in arr1 to find the median.

Pseudo code

1. IF m1 == m2 return m1

2. ELSE IF m1 < m2

3. find median of arr1[mid to n] and arr2[0, mid-1]

4. ELSE IF m1 > m2

5. find median of arr2[mid to n] and arr1[0, mid-1]

6. END