# Exercise 9.3.8

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$.

This was fun!

- If the two arrays are of length $1$, we pick the lower of the two elements
- We the two medians of the array
- We 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 $\lfloor n / 2 \rfloor$ elements
- We solve the problem for the new arrays

Let's reason about why this works. Since we have $2n$ elements, we know that
the length is an even number and we're looking for a lower median. We need to
observe that the median we're looking for is between the medians of the two
arrays. Let's elaborate on that.

Let's assume that the median is at position $k$ in array $A$. This means that
there are $k - 1$ elements less than the median in $A$ and $n - k$ elements
greater than the median in $B$. If $k < n / 2$ then the median of $A$ will be
greater than the final median, but the median of $B$ will be lesser than it.
It's the other way around for $k \ge n / 2$. Thus the median of the two arrays
is always between the medians of each.

Step 3 removes the same number of elements from each array, half of which are
greater than the median and half of which are less than it. This reduces the
subproblem to two smaller arrays that are sorted and their elements have the
same median.

### Python code

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