Comment trouver les k voisins les plus proches de la médiane de n numéros distincts en O(n) le temps?

Je peux utiliser la médiane des médianes algorithme de sélection pour trouver la médiane en O(n). Aussi, je sais qu'une fois que l'algorithme est terminé, tous les éléments à gauche de la médiane sont moins que la médiane et tous les éléments à droite sont supérieures à la médiane. Mais comment puis-je trouver les k voisins les plus proches de la médiane en O(n) le temps?

Si la médiane est n, les nombres à gauche sont inférieurs à n et les chiffres à la droite sont plus grande que n.
Toutefois, le tableau n'est pas trié dans la gauche ou la droite. Les chiffres sont tout ensemble des différents chiffres donnés par l'utilisateur.

Le problème de l'Introduction des Algorithmes par Cormen, problème 9.3-7

Si la médiane ont été en emplacement n, vous êtes à la recherche pour les valeurs à l'emplacement de n+1 et l'emplacement de n-1?
Les chiffres sont bignums ou point fixe entiers?

OriginalL'auteur Anonymous | 2009-10-13