Suppose you are given two sorted lists A and B of n element

Suppose you are given two sorted lists, A and B , of n elements each, all of which are distinct. Describe a method that runs in O (log n ) time for nding the median in the set dened by the union of A and B .

Solution

Median: is usually described as the number separating the higher half of a sample or a population, or a probability distribution, from the lower half.

The median of a sorted list of numbers, can be found, by arranging all the numbers from lowest value number to highest value number and then picking the middle number.

Comparing the medians of two sorted lists

In this method we will first obtain the medians of the two sorted lists and then we will compare them.

Suppose we are given two sorted lists A and B.

Algorithm:

1) Calculate the medians m1 and m2 from given list A and B respectively.

2) If m1 and m2 both are equal then return either m1 or m2.

3) If m1 > m2, then median is present in one of the below two sublists.

a) From first element of A1 to m1 (A1[0...|n/2|])

b) From m2 to last element of B2 (B2[|n/2|...n-1])

4) If m2 >m1, then median is present in one of the below two sublists.

a) From m1 to last element of A1 (A1[|n/2|...n-1])

b) From first element of B2 to m2 (B2[0...|n/2|])

5) Repeat the above steps until size of both the sublists becomes 2.

6) If size of the two lists is 2 then use this formula to get the median.

Median = (max(A1[0], B2[0]) + min(A11, A21))/2

Time complexity for above algorithm is O(log n)