Friday, March 18, 2011

Median of two sorted arrays

This question is similar to the previous question which can solved in O(logn) using binary search approach. Lets see the algorithm….

Algorithm
1.Let the two arrays be a1,a2 with n elements each with n elements
2.Let med1 and med 2 be the medians of two arrays respcetively
3.if med1==med2 means the required median is med1(or med2)
4.if med1 < med2 that means the median can either lie in upper half of a1 or lower half  of a2     5.if med1 >med2 that means the median can be in lower half of of a1 or upper half of a2
we continue this process until two elements are present in the array
if two elements are present in the array then we calculate the median as follows
median_required = (max(a1[0],a2[0])+min(a1[1]+a2[1])) /2

No comments: