Поиск элемента k'th в несортированном массиве с использованием внешней функции

Question

Мне нужно разработать алгоритм, который найдет k'th наименьший элемент в несортированном массиве, используя функцию, которая называется «MED3»: Эта функция находит n/3 (этаж) и 2n/3 (ceil) элементов массива, если он был отсортирован (очень похож на медианный, но вместо n/2 он возвращает эти значения).

Я думал о типе разделов вокруг этих двух значений, а не о том, чтобы продолжить, как QuickSelect, но проблема в том, что «MED3» не возвращает индексы двух значений, а только значения.

например, если массив равен: 1, 2, 10, 1, 7, 6, 3, 4, 4 он возвращает 2 (значение n/3) и 4 (значение 2n/3).

Я также решил запустить массив и взять все значения между 2 и 4 (например, в данном массиве выше) в новый массив, а затем снова использовать «MED3», но может быть дубликат (если array - 2, 2, 2, 2, ..., 2 Я бы каждый раз принимал все элементы).

Любые идеи? Я должен использовать «MED3». * MED3 похож на черный ящик, он работает в линейном времени.

спасибо.

Answer 1

Я думаю, что вы на правильном пути, но вместо того, чтобы принимать от 2 до 4, я предлагаю удалить первые значения n/3, которые являются < = MED3.floor() и первые значения n/3, которые > = MED3.ceil(). Это позволяет избежать проблем со слишком большим количеством дубликатов. Если два прохода/цикл не слишком дороги, вы можете удалить все значения < MED3.floor() + до общего количества n/3 значений = MED3.floor() (сделать то же самое для ceil())

затем повторите, пока вы не достигнете наименьшей цели k'th.