Pesquisa sequencial

BCC202 – Aula 21
Algoritmos e Estruturas de Dados I

Pesquisa em Memória Primária
• Introdução - Conceitos Básicos
• Pesquisa Sequencial
• Pesquisa Binária
• Transformação de Chave (Hashing)‫‏‬
• Listas Encadeadas
• Endereçamento Aberto
• Hashing Perfeito

• Árvores de Pesquisa
• Árvores Binárias de Pesquisa
• Árvores AVL

Introdução – Conceitos Básicos
• Estudo de como recuperar informação a partir de uma grande massa de informação previamente armazenada. • A informação é dividida em registros.
• Cada registro possui uma chave para ser usada na pesquisa. • Objetivo da pesquisa: Encontrar uma ou mais ocorrências de registros com chaves iguais à chave de pesquisa.
• Pesquisa com sucesso X sem sucesso.

Introdução – Conceitos Básicos
• Tabelas
• Conjunto de registros ou arquivos ⇒ TABELAS
• Tabela: associada a entidades de vida curta, criadas na memória interna durante a execução de um programa.
• Arquivo: geralmente associado a entidades de vida mais longa, armazenadas em memória externa.
• Distinção não é rígida:
§ tabela: arquivo de índices.
§ arquivo: tabela de valores de funções.

Método de Pesquisa mais Adequado
• Depende principalmente:
1. Quantidade dos dados envolvidos.
2. Arquivo estar sujeito a inserções e retiradas freqüentes.

• Se conteúdo do arquivo é estável é importante minimizar o tempo de pesquisa, sem preocupação com o tempo necessário para estruturar o arquivo

Algoritmos de Pesquisa - TADs
• É importante considerar os algoritmos de pesquisa como tipos abstratos de dados (TADs), de tal forma que haja uma independência de implementação para as operações. • Operações mais comuns:
1. Inicializar a estrutura de dados.
2. Pesquisar um ou mais registros com determinada chave.
3. Inserir um novo registro.
4. Retirar um registro específico.

Dicionário
• Operações mais comuns:
5. Ordenar um arquivo para obter todos os registros em ordem de acordo com a chave.