test2
Busca ou Pesquisa
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.
Busca ou Pesquisa
Tabela ou Arquivo: termos genéricos, pode ser qualquer
estrutura de dados usada para armazenamento interno e organização dos dados.
Uma tabela é um conjunto de elementos, chamados
registros.
Existe uma chave associada a cada registro, usada para
diferenciar os registros entre si.
Busca ou Pesquisa
A tabela pode ser:
Um vetor de registros;
Uma lista encadeada;
Uma árvore;
Etc.
A tabela pode ficar:
Totalmente na memória (busca interna);
Totalmente no armazenamento auxiliar (busca externa);
Dividida entre ambos.
Busca ou Pesquisa
As técnicas de busca em memória interna que estudaremos
serão:
Busca Sequencial;
Busca Binária;
O objetivo é encontrar um dado registro com o menor
custo.
Cada técnica possui vantagens e desvantagens
Busca ou Pesquisa Sequencial
A busca sequencial é a forma mais simples de busca.
É aplicável a uma tabela, como um vetor ou como uma lista
encadeada.
Busca mais simples que há.
Percorre-se registro por registro em busca da chave.
Busca ou Pesquisa Sequencial
Esse método deve ser usado em dados desordenados, mas
também pode ser aplicado a dados ordenados.
É fácil de ser codificada.
Funciona da seguinte forma:
a partir do primeiro registro, pesquise sequencialmente até encontrar a chave procurada;
então pare;
Características
Extremamente simples o algoritmo.
Pode ser muito ineficiente quando o conjunto de dados é
muito grande.
Desempenho Computacional
Pior Caso: é quando é necessário realizar n comparações