Possible Duplicate:
Como encontrar o k-ésimo elemento em uma matriz não classificada de comprimento n em O (n

Atualmente, estou sentado na frente de um trabalho do curso. A tarefa é encontrar o enésimo menor elemento em uma matriz. (Sem classificá-lo!)

Eu tentei entender o algoritmo BFPRT, mas pelo que consegui, só é útil se você quiser calcular a mediana e não o "n-ésimo menor" element

Outra idéia que tive foi converter a matriz em uma árvore, anexando nós menores / maiores à esquerda / direita do nó raiz. Não tenho certeza, no entanto, se isso conta como classificação. Para acelerar isso, eu poderia armazenar o número de subnós em cada n

A atribuição completa também inclui que o algoritmo deve ser recursivo. Há também a dica para pensar em outras estruturas de dado

O que você acha da minha ideia de transformar a matriz em uma árvore equilibrada?

Existem outras opções que eu possa ter perdido?

EDIT: Examinei várias perguntas semelhantes, mas não consegui entender completamente as respostas / aplicá-las à minha tarefa específic