Ex 9.3-8 of Introduction to algorithms

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