Algoritmos para Pesquisa

Algoritmos para Pesquisa

1. LINEAR / sequencial

   • Objetivo
     • Localizar um elemento em um conjunto.
   • Exemplos de conjuntos
     • Vetores de tipos primitivos.
     • Vetores de objetos.
     • Coleções.
   • Chave
     • Identifica o elemento a ser localizado.
   • Requisito
     • Deve haver somente um elemento com a chave procurada.
   • Método
     • Percorrer o vetor da esquerda para a direita
     • Comparar a chave com cada elemento do vetor, se a chave equivale ao elemento, retornar a posição do mesmo.
     • Se o elemento não for localizado, retornar -1
   • Exemplos
   • Análise de Eficiência
     • Número de passos
       • Cenários
         • MELHOR: a chave está na primeira posição.
         • PIOR: a chave está na última posição.
         • MÉDIA: P = E / 2 onde P = número total de passos E = número de elementos
       • EXEMPLO: VETOR COM 100 ELEMENTOS
         • MELHOR cenário: 1 passo.
         • PIOR cenário: 100 passos.
         • MÉDIA: 100 / 2 = 50 passos.
   • Consiste em percorrermos o vetor, elemento a elemento, verificando se o elemento de interesse é igual a um dos elementos do vetor;

2. BINÁRIA

   • Objetivo
     • Localizar um elemento em um conjunto.
   • Exemplos de conjuntos
     • Vetores de tipos primitivos.
     • Vetores de objetos.
     • Coleções.
   • Chave
     • Identifica o elemento a ser localizado.
   • Mais eficiente que a pesquisa LINEAR
   • Requisitos
     • Deve haver somente um elemento com a chave procurada.
     • Os elementos devem estar ordenados.
   • Métodos
     • Iniciar no meio do espaço de busca.
     • A cada comparação, elimina-se metade das possibilidades.
       • Se a chave é igual, o elemento foi procurado.
       • Se a chave é maior, o elemento está à esquerda.
       • Se a chave é menor, o elemento está à direita.
   • Análise de Eficiência
     • Número de passos
       • Cenários
         • MELHOR (a chave está na primeira posição analisada): 1 passo.
         • PIOR (a chave está na última posição analisada): P = log² (E)
         • MÉDIA: P = log² (E) / 2 ONDE P = número total de passos E = número de elementos
       • EXEMPLO: VETOR COM 100 ELEMENTOS
         • MELHOR cenário: 1 passo.
         • PIOR cenário: log² (100) = 6,644 (7 passos).
         • MÉDIA: log² (100) / 2 = 3,322 (4 passos).
     • Função logarítmica
       • Fórmula
         • P = log² (N)
       • Notas
         • O logaritmo na base 2 de um número N indica a quantidade de vezes que o 2 precisa ser multiplicado por ele próprio até que o resultado seja igual a este número N.
         • A maioria das calculadoras possuem uma função para calcular o logaritmo de um número na base 10. A conversão desse resultado para a base 2 pode ser feita multiplicando-o pela constante 3,322.
           • log¹º(100) = 2 log¹º(100) = 2 * 3,322 = 6,644
   • É pesquisar o elemento que buscamos com o valor do elemento armazenado no meio do vetor com dados ordenados.

3. Operação realizada sobre registros.

4. Objetivo: Localizar um registro.

Bilder und Dateien der Mindmap