Finding median of 2 sorted arrays in O(log n)

Question

If there are given two arrays, A and B, each containing n real numbers in sorted order. How to compute the median of all the numbers in A and B, in O(log n) time. I have to make an algorithm that takes at most logarithmic time.

My idea:

A = 1, 3, 6, 8, 10, 15, 20

B = 1, 2, 3, 7, 10, 30

C = sort(A, B)

a = len(A) // 7
b = len(B) // 6
M = (a+b)/2 // 6.5
if M is a fraction:
    Median = C[M+0.5]
else:
    Median = (C[M]+C[M+1])/2

How to write sort function under complexity O(log n)? I don't even have to sort all the elements of A and B, I only need the first M+1 elements of C because of above method.

Answer 1

There are two arrays: $A, B$ with lengths $n, m$. Finding median in the sorted array takes constant time (just access middle element or take a mean of two center elements).

To find the median of all elements in $\mathcal O(min(\log n, \log m))$ perform the following steps:

1. If $(length(A) \le 2$ or $length(B) \le 2)$ or $(A _{last} \le B_{first}$ or $B_{last} \le A_{first})$ calculate median and return.

2. Set $A_m = median(A), B_m = median(B)$ and compare them. If $A_m = B_m$ return result. If $A_m < B_m$ then discard first half of $A$ and the same amount of elements from the second half of $B$. else if $A_m > B_m$ then discard second half of $A$ and the same amount of elements from the first half of $B$.

3. Goto 1

This algorithm runs in logarithmic time. Minimum in the complexity reflects the fact that when the smaller array has length $\le 2$ the procedure terminates. At step 2 the both arrays get halved (or procedure is terminated) so it will be performed at most $\log_2(min(n, m))$ times.

By calculate median there are two cases: at least one arrays length was $\le 2$, so shift the median of the second array accordingly, or arrays do not overlap (or share the boundary element) then the median is the center element of two arrays concatenated in ascending order. In fact only index is calculated, no actual concatenation takes place.

Why the procedure stops when at least one of lengths is $\le 2$? Consider the corner case, e.g. A = [2, 9], B = [3, 11], the median is 6, but taking them separately yields 5.5 and 7, which in turn yields incorrect result 6.25.

For example:
$A = [1, 2, 6, 8, 12, 15], B = [2, 5, 8, 15]$ to keep an overview, the whole sorted array $C = [1, 2, 2, 5, 6, 8, 8, 12, 15, 15], C_m = 7$.
$A_m = 7, B_m = 6.5$ now $A_m > B_m$ so we drop [12, 15] from $A$ and we drop [2, 5] from $B$. Why $8$ is not dropped from $A$? Bacause we cannot drop $8$ from $B$, and in order to preserve median we can only drop the same number of elements ftom the both arrays at the opposite sites of the mean.
So $A = [1, 2, 6, 8], B = [8, 15]$. Now back to step 1, the arrays do overlap by common element at the end so we take $AB$, the lengths are 4, 2, so it is a mean of 3rd and 4th element $\frac{6 + 8}{2} = 7$.