kth smallest element in n sorted arrays

kth smallest in one sorted array, just take O(1) time

kth smallest in two sorted arrays, there is a binary search algorithm, take O(log k) time

kth smaleest in n sorted arrays, we can use min-heap, takes O(k log n). However, when n = 1 or 2, it's essential brute-force linear scan which takes O(k).

Is there more optimized algorithm for kth smallest in n sorted arrays which will keep optimized when n = 2?

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