1. java
  2. android
  3. c#
  4. .net
  5. javascript
  6. php
  7. jquery
  8. html
  9. sql

Como fazer uma busca binária com template

Estou terminando um trabalho, e o que falta é só criar uma função que busca elementos de uma lista sequencial ordenada com templates, baseada em uma busca binária.

A classe LLSeqOrd é uma classe herdada da LLSeq, e a função abstrata buscaAux, que tem a seguinte assinatura:

virtual int buscaAux( Chave _x ) const = 0;

Há outra classe que herda LLSeq, a LLSeqReg, que não usa função de comparação como a busca binária, portanto não posso mudar a assinatura.

template <typename Chave, typename Informacao>
int LLSeqOrd<Chave, Informacao>::buscaAux( Chave _x ) const {

    /* Limite inferior da lista. */
    int l = 0;
    /* Limite superior da lista. */
    int r = this->mi_Length - 1;
    /* Item procurado da lista. */
    int i = this->mi_Length;
    /* Elemento central da lista. */
    int m;

    /* O código reexecuta até que o r seja menor que o l. */
    while ( r >= l ) {

        /* Atribui o elemento central da lista. */
        m = ( l + r )/2;

        /* Se o elemento central for maior que o procurado. */
        if ( this->mpt_Data[ m ].id > _x ) {
            /* O procurado é o elemento central. */
            i = m;
            /* Atualiza o limite superior da lista. */
            r = m - 1;

        /* Se o elemento central não for maior que o procurado. */
        } else {
            /* Se o elemento central for igual ao procurado. */
            if ( this->mpt_Data[ m ].id == _x ) {
                /* Retorna o elemento procurado. */
                return m;

            /* Se o elemento central for menor que o procurado. */
            } else {
                /* Atualiza o limite inferior da lista. */
                l = m + 1;
            }
        }
    }

    /* Retorna o tamanho da lista caso o elemento procurado não seja encontrado. */
    return i;
}
  • Os templates são usados para substituir o que normalmente usamos generics ou interfaces. No caso da busca, por exemplo, estamos falando do tipo da lista e da função de comparação. Não entendi muito bem onde está sua dúvida, pois seu método já usa templates.

    ViniGodoy   21 de abr de 2015
  • Vou editar a pergunta para explicar melhor.

    Breno Mauricio   21 de abr de 2015
  • Vê se a pergunta ficou mais clara.

    Breno Mauricio   21 de abr de 2015
  • Pensei em uma solução, mas não sei se posso usá-la, tô esperando meu professor me responder a dúvida. Eu perguntei a ele se eu poderia usar sobrecarga de métodos, e sempre chamar essa função com um ponteiro para uma função de comparação, mas caso seja nulo, então a ideia seria que os elementos são objetos que possuem métodos operadores (==, <, >) e retornava a função da assinatura do pai. Entendeu minha ideia?

    Breno Mauricio   21 de abr de 2015
  • Lembrei que se fizesse isso teria que alterar outra função e não posso.

    Breno Mauricio   21 de abr de 2015
Mostrar todos os 7 comentários>
  1. Você vai ver essas setas em qualquer página de pergunta. Com elas, você pode dizer se uma pergunta ou uma resposta foram relevantes ou não.
  2. Edite sua pergunta ou resposta caso queira alterar ou adicionar detalhes.
  3. Caso haja alguma dúvida sobre a pergunta, adicione um comentário. O espaço de respostas deve ser utilizado apenas para responder a pergunta.
  4. Se o autor da pergunta marcar uma resposta como solucionada, esta marca aparecerá.
  5. Clique aqui para mais detalhes sobre o funcionamento do GUJ!

0 resposta

Não é a resposta que estava procurando? Procure outras perguntas com as tags c++ ou faça a sua própria pergunta.