kth smallest element in n sorted arrays

I think something like this could work:

Given $n$ arrays $A_1, …, A_n$ and an integer $k$, finding the $k$-th smallest element of those arrays can be done by finding $n$ "cuts" in those arrays such that the total number of elements before cuts is equal to $k$. The $k$-th smallest element is then one of the elements just before cuts in one of the arrays.

In details, if the arrays are of lengths $N_1, …, N_n$, we need to find indices $i_1, …, i_n$ such that for all $1\leqslant j \leqslant n$, we have $0\leqslant i_j\leqslant N_j$, and $\sum\limits_{j=1}^ni_j = k$.

To ensure the cuts are well done, for $j\neq j'$, we also need $A_j[i_{j}-1] \leqslant A_{j'}[i_{j'}]$.

The $k$-th smallest element is then $\max\limits_{j=1}^nA_j[i_{j}-1]$ (note that some of those may not exist if $i_j=0$).

The idea of the algorithm is some kind of double divide and conquer. Details may be missing, but I think this works:

• if $n = 1$, find the cut in $\mathcal{O}(1)$ time;
• otherwise:
  • let $k_1 = 0$ and $k_2 = k$;
  • while $k_2 > k_1 + 1$:
    • let $\ell = (k_1 + k_2) / 2$
    • find the cuts for the $\ell$-th smallest element $x$ in arrays $A_1, …, A_{\frac{n}2}$;
    • find the cuts for the $(k-\ell)$-th smallest element $y$ in arrays $A_{\frac{n}2+1},…,A_n$;
    • if the cuts are well done, return $\max(x, y)$;
    • otherwise, if $x < y$, $k_1$ becomes $\ell$;
    • otherwise, $k_2$ becomes $\ell$

To check if cuts are well done, you need to check if $x \leqslant A_{j'}[i_{j'}]$ for $j'\in \{\frac{n}2+1, …, n\}$ and if $y\leqslant A_{j'}[i_{j'}]$ for $j'\in \{1, …, \frac{n}2\}$.

For the complexity, let $C(n)$ be the time complexity for the search of the $k$-th smallest element in $n$ sorted arrays. Given the previous algorithm, we get: $$C(n) = \log_2 k (2C\left(\frac{n}2\right) + \mathcal{O}(n))$$

Using the master theorem, we get $C(n) = \mathcal{O}(n(\log_2 k)^{\log_2 n})$.

We get $C(1) =\mathcal{O}(1)$ and $C(2) = \mathcal{O}(\log_2 k)$.