Consider two arrays, A and B, each of which contains n integers. The elements in
ID: 3852486 • Letter: C
Question
Consider two arrays, A and B, each of which contains n integers. The elements in each array are in sorted order, i.e. A[0] lessthanorequalto A[1] lessthanorequalto .. lessthanorequalto A[n - 1] and B[0] lessthanorequalto B[1] lessthanorequalto .. lessthanorequalto B[n - 1]. Give as fast an algorithm as you can for finding the median value of all the 2n numbers in both A and B. (We define the median of 2n numbers to be the average of the nth smallest and nth largest values.) Argue that your algorithm is correct and give its running time.Explanation / Answer
We can use Divide and Conquer approach to find the Median in O(log n) time
Lets see How :-
1) Find the median p1 and p2 of the two arrays A[] and B[]
2) If both p1 and p2 are equal then we have found our median just simply return p1 or p2
3) If not, then we need to check if p1 is greater then p2 , then median is in the one of the below two subarrays
a) From first element of A to p1 (A[0.......n/2 ])
b) From p2 to last element of B (B[n/2.......n-1 ])
4) If not, then we need to check if p2 is greater then p1 , then median is in the one of the below two subarrays
a) From p1 to last element of A (A[n/2.......n-1 ])
b) From first element of B to p2 (B[0.......n/2 ])
5) Keep executing the above statements until the size becomes 2
6 ) If the size becomes 2 then , M = ( Max( A[0] + B[0] ) + Min( A[1] + B[2] ) ) / 2
The overall Complexity is O(log n)
Programming paradigm is Divide and Conquer . As it divides the problem into sub problems and reduces the time and area to work on.