[Solved]: Finding median of three sorted array (the same length)

Problem Detail: 

I think about following problem:
There are given three sorted arrays $A,B,C$ (each of them is length $n$).
Every array has distinct elements. Find median of union $A,B,C$.

I consider following approach:
Let's consider $A_i, B_i, C_i$, where $i=n/2$. There are six cases - but I consider only one (rest of them is analogous). Let $A_i\le B_i\le C_i$: Now we may dispse $1/3$ elements - $A[1...n/2]$ and $C[n/2 + 1... n]$.
Unfortunately I can't estimate time of run this algorithm.
I should solve recusrion equality: $T(n) = T(2/3n) + 1$
$(T(0) = T(1) = 1$, but I can't.

I am thinking about better algorithm. Can you suggest something ?

Edit
I am goint to say more about this algorithm. The key idea is using Divide and conquer method. In each step we may dispose $\frac{1}{3}$ elements. Lets $i = n/2$. Let suppose that $A_i \le B_i \le C_i$ (rest of cases is analogous). Look at example:

In every case I dispose $1/3$ elements and get smaller problem.

Asked By : user40545

Answered By : Lieuwe Vinkhuijzen

The recurrence relation can be solved as follows: for large $n$,

$$T(n) = T\left(\frac{2}{3}n\right) + 1 = T\left(\frac{2^{2}}{3^{2}}n\right) + 2 = \cdots = T\left(\left(\frac{2}{3}\right)^kn\right)+k$$

This iterative process ends when a $T(m)$ is called with $m \leq 1$. Now for what $k$ do we have $\frac{2^{k}}{3^{k}}n \leq 1$? It is $ ^{\frac{3}{2}}log(n)$. (verify this for yourself)

A good way to do this is using an insight from the $\texttt{MergeSort}$ algorithm. It sorts an algorithm by consequtively merging increasingly long sorted substrings. Here's how it goes: you keep three indices, say $i,j,k$, which start at $0$. You iterate them over the three arrays, each time incrementing the index which points to the highest value of its respective array, until you've encountered half of all elements, i.e. $i+j+k=\frac{3n}{2}$. When that has happened, you have encountered the median. Here's this algorithm as pseudocode:

$\texttt{TernaryMedian}(\texttt{array } A, \texttt{array } B, \texttt{array } C):$

int $i, j, k :=0$

while $i+j+k < \frac{3n}{2}$ do

$\quad$ if $A_i > B_j$ then

$\quad\quad$ if $A_i > C_k$ then $i := i + 1$

$\quad\quad$ else $k := k + 1$

$\quad$ else if $B_j > C_k$ then $j := j + 1$

$\quad$ else $k := k + 1$

end while

$median := max(A_i, B_j, C_k)$

This algorithm runs in time $O(n)$ and makes $3n$ comparisons in the best case and $\frac{9}{2}n$ comparisons in the worst; I'll leave the average case to you. This algorithm can be improved if you keep a pointer to the array containing the highest value of any of the pointers but which was not the subject of last iteration's increment. I'll leave it up to you to figure out why. Then you get $\frac{3}{2}n+1$ comparisons in the best case and $3n$ comparisons in the worst.

It may help to first look up $\texttt{MergeSort}$ on Wikipedia for merging two substrings, and then think about how you would merge three substrings. Hope this helps.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47865