9.3-9

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 .
If X is an array that has 1..n and let median m occurs at X[k]. Then there k elements less than equal m and n-k elements greater than equal m.If we combine both arrays X and Y the no of elements is 2n. If m is a median after combining two arrays it should have n to its left and n elements to the right including m. So for the left side to have n there n-k less than or equal to m(let x be no of elements in y which less than or equal to m n = k+x then x = n-k ). similarly for the right side k elements greater than or equal to m(let x be no of elements in y which greater than or equal to m n = n-k+x). If we can an in equality. $$Y[n-k] \leq X[k] \leq Y[n-k+1]$$ But we need to also consider when k = n. Then Y[0] will have any elements and $X[n] \leq Y[1]$. If the median k' > k then X[k] will not satisfy the above equation. Then $$X[k] \lt Y[n-k]$$. Similarly if we have K' < k then X[k] > Y[n-k+1]. Similarly the median can occur in X or Y. If it occurs Y array the comparisions will have the array names reversed(replace x with Y and Y with X).We can use above analysis to write the algorithm. We can use binary search to find the median.

FIND-TWO-ARRAY-MEDIAN(X,Y)
n = A.length
median = FIND-MEDIAN(X,Y,1,n,n)
If median not found
FIND-MEDIAN(Y,X,1,n,n)
return median
FIND-MEDIAN(X,Y,low,high,n)
If low < high
k = (low+high)/2
If k = n and X[n] = Y[1] then
return X[n]
else if $Y[n-k] \leq X[k] \leq Y[n-k+1]$
return X[k]
else if $X[k] > Y[n-k+1]$
FIND-MEDIAN(X,Y,low,k-1,n)
else
FIND-MEDIAN(X,Y,k+1,high,n)