Выберите в объединении отсортированных массивов: уже известно?

Я ищу библиографические ссылки для следующего алгоритма / проблемы: я назвал его "BiSelect" или "t-ary Select" или "Select in Union of Sorted Arrays", но я предполагаю, что он был представлен ранее под другим именем?

проблема

Рассмотрим следующую проблему:

Для заданных непересекающихся отсортированных массивов A 1 , … , A k соответствующих размеров n 1 , … , n k и целого числа t ∈ [ 1 .. ∑ n i ] , каково t- ое значение их отсортированного объединения ∪ я а я ?$k$$A_1,\ldots, A_k$$n_1,\ldots,n_k$$t\in[1..\sum n_i]$$t$ $\cup_i A_i$

Решения

$O(\lg\min\{n_1,n_2,t\})$$k=2$$k=2$$A_1[t/2]$$A_2[t/2]$$A_1[t/2..t]$$A_2[1..t/2]$$A_1[1..t/2]$$A_2[t/2..t]$$t/2$$n_1$$n_2$$t$

Это обобщает чуть более сложный алгоритм, работающий во времени для больших значений , основанный на вычислении медианы значений для : Наименьшие элементы могут далее игнорироваться в массивах где меньше, чем медиана, а элементы рангов в могут далее игнорироваться в другие массивы, приводящие к уменьшению вдвое в каждом повторении (и стоимости для медианы).$O(k\lg t)$$k$$A_i[t/k]$$i\in[1..k]$$t/k$$k/2$$A_i[t/k]$$[t-t/k..]$$k/2$$t$$O(k)$

Ссылки?

Я доволен своим решением (ями), но полагаю, что проблема (и ее решение) уже были известны. Он связан с алгоритмом линейного времени для вычисления медианы (путем сортировки групп по размеру и рекурсии по медиане их середин), но является несколько более общим. Я спросил несколько колледжей в Мадальго в Орхусе (Дания), а затем несколько других на семинаре по стрингологии (Руан), но безуспешно: я надеюсь, что кто-то, кто более опытен, может помочь в обмене стеками ...$5$

Мотивы

Решения этой проблемы имеют приложения к отложенной структуре данных для массивов (действительно, это можно рассматривать как оператор в отложенной структуре данных для объединения отсортированных массивов); и в более запутанном виде, к адаптивному вычислению оптимальных кодов без префиксов.

Алгоритм, описанный Фредериксоном и Джонсоном в 1982 году, считает, что все множества имеют одинаковый размер. Они также описали в 1980 году оптимальное решение, которое использует преимущества различных размеров отсортированных наборов. Сложность этого алгоритма находится в пределах .$O(k + \sum^k_{i=1}\log{n_i})$

Ссылка

Грег Н. Фредериксон и Дональд Б. Джонсон. 1980. Обобщенный отбор и ранжирование (Предварительная версия). В материалах двенадцатого ежегодного симпозиума ACM по теории вычислений (STOC '80). ACM, Нью-Йорк, Нью-Йорк, США, 420-428. DOI = 10.1145 / 800141.804690 http://doi.acm.org/10.1145/800141.804690

Фредериксон и Джонсон получили оптимальный результат в 80-х годах. Пусть , тогда существует алгоритм, решающий вашу задачу в .$p=\min(k,t)$$O(k+p \log \frac{t}{p})$

Ссылка

Г. Н. Фредериксон, Д. Б. Джонсон " Сложность выбора и ранжирования по x + y и матрицам с отсортированными столбцами " J. Comput. System Sci., 24 (2) (1982), с. 197–208

Случай k = 2 возникает в параллельной сортировке слиянием, поскольку объединение двух отсортированных массивов из разных потоков необходимо разделить между двумя потоками, чтобы поддерживать одинаковую степень параллелизма. Это домашнее решение является одним из примеров.