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)$$.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 46, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://cs.stackexchange.com/questions/152771/kth-smallest-element-in-n-sorted-arrays", "fetch_time": 1708947831000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-10/segments/1707947474659.73/warc/CC-MAIN-20240226094435-20240226124435-00701.warc.gz", "warc_record_offset": 178164518, "warc_record_length": 39350, "token_count": 871, "char_count": 2484, "score": 3.515625, "int_score": 4, "crawl": "CC-MAIN-2024-10", "snapshot_type": "latest", "language": "en", "language_score": 0.7374992966651917, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00043-of-00064.parquet"}