Pesquisa Sequencial E Bin Ria

Algoritmos e Estruturas de Dados I
Análise de Complexidade de Algoritmos

Curso de Engenharia de Computação
CEFET-MG
2015/1

Análise de complexidade de algoritmos


O problema da Pesquisa




Verificar a presença ou não de um dado elemento em um conjunto Algoritmos para o problema da pesquisa


Pesquisa sequencial em vetor não ordenado



Pesquisa sequencial em vetor ordenado



Pesquisa binária



Soluções mais avançadas

Problema: busca/pesquisa/procura em vetor


Problema






dado um conjunto de elementos, verificar se um dado elemento ocorre no conjunto pesquisa ou busca ou procura – search

Há vários algoritmos e estruturas de dados para este problema:


pesquisa sequencial em vetor (array) não ordenado



pesquisa sequencial em vetor ordenado



pesquisa binária



hashing



árvores de pesquisa (AEDS2)

Classificação dos resultados da pesquisa




Duas respostas possíveis
 o elemento está presente
 o elemento não está presente

Dois casos para análise de complexidade


pesquisa com sucesso




o item procurado está presente no vetor ou arquivo

pesquisa sem sucesso




=> sucesso
=> insucesso

o item procurado não está presente no arquivo

A análise de complexidade é feita separadamente para cada um destes casos

Algoritmos para o problema da pesquisa



Pesquisa sequencial em vetor não ordenado



Pesquisa sequencial em vetor ordenado



Pesquisa binária

Pesquisa sequencial em vetor


Vetor não ordenado: caso mais simples de pesquisa



Entrada
 o vetor preenchido com os elementos do conjunto (registros ou estruturas)  o item procurado: chave de um registro (estrutura)



Algoritmo
 comparar sequencialmente cada elemento do vetor com o item procurado até que
 o item é encontrado: retornar o registro, a posição, etc.
 o fim do vetor é encontrado: indica pesquisa sem sucesso

Exemplo: pesquisar o elemento 2 no vetor

Sucesso: o elemento está presente

Algoritmo: pesquisa sequencial em vetor NÃO ordenado