Scribd
Upload
7 views4 pages

O(log n) Median Finding Algorithm

Uploaded by

wuyuman6
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views4 pages

O(log n) Median Finding Algorithm

Uploaded by

wuyuman6
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CS583: Analysis of Algorithms

Dr. Fei Li
Department of Computer Science
Assignment 3 — Medians and order statistics

Problem
Let X [1, . . . , n] and Y [1, . . . , n] be two arrays, each containing n
numbers already in sorted order. Give an O(lg n)-time algorithm to
find the median of all 2n elements in arrays X and Y .
def two_array_median(a, b):
if len(a) == 1:
return min(a[0], b[0])

m = median_index(len(a))
i=m+1
if a[m] < b[m]:
return two_array_median(a[-i:], b[:i])
else:
return two_array_median(a[:i], b[-i:])

def median_index(n):
if n % 2:
return n // 2
else:
return n // 2 - 1
[Link] the two arrays are of length 1 we pick the lower of the two
elements.
[Link] the two medians of the array
[Link] take the lower part of the array with the greater median and
the upper part of the array with the lesser median. If each array
has n elements, we take the first/last n/2 elements.
[Link] solve the problem for the new arrays

You might also like