Нахождение k-го квантиля набора из n элементов. (Из cormen)

k-ые квантили набора из n элементов - это статистика порядка k - 1, которая делит отсортированный набор на k равных размеров наборы (с точностью до 1). Приведите алгоритм за время O (n lg k) для перечисления k-ых квантилей набора.

Прямым решением было бы выбрать каждые k, 2k, 3k ... ik наименьшего элемента, время работы которого равно O (kn) (k вызывает процедуру выбора O (n)). Но это можно оптимизировать, чтобы добиться большего, чем O (kn). n], а также рекурсивно выбрать k-й наименьший элемент в левом подмассиве A [0 ... i].

Основным вызовом будет просто select (A, k, n).