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:

Post a Comment