**Question**:

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.

**Answer**:

Without losing generality, suppose the median

**z**is the smaller median (there are two medians since total number is even), it's the ith element in array X. In array X, there are i-1 numbers smaller than z and n-i numbers larger than the z. Because z is the median of all 2n elements, there should be n-i numbers in Y smaller than z and i numbers larger than z.

In order to find out z, we first compare the median of X and Y. Say they are

*mx*and

*my*respectively. If

*mx*is smaller than

*my*, we compare

*mx*and the largest element in Y that is smaller than

*my*, say it's

*my2*. If

*mx*is larger than my2, then

*mx*is z, the median of all 2n elements. Otherwise, z must be in higher half of X or lower half of Y. So, we can perform preceding logic recursively.

This algorithm works just like binary search tree whose running time is O(lg n).

The code for the algorithm is available at:

http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/algorithm/i2a_ex_9.3-8/ex9_3_8.cpp

## No comments:

Post a Comment