Busca Sequencial
Por: Fernanda Cristina Lourenço • 20/9/2015 • Pesquisas Acadêmicas • 1.251 Palavras (6 Páginas) • 570 Visualizações
Classificação e Pesquisa |
Pesquisa Sequencial |
Índice[pic 1]
Introdução 3
Pesquisa Sequencial 4
Exemplo de Busca Sequencial Simples 4
Sentinela 6
Referências Bibliográficas 7
Introdução
Pesquisa é a recuperação de informação a partir de uma grande massa de dados armazenados previamente. Essas informações são divididas em registros e cada registro possui uma chave que será usada na pesquisa, como o seu índice. O objetivo da pesquisa é encontrar ocorrências de registros nessas informações que sejam iguais à chave de pesquisa. Algumas aplicações podem ocorrer em contas de banco ou sistemas de reservas de passagens aéreas.
A escolha do método de busca deve levar em consideração a quantidade de dados armazenados e frequência com que as operações mais comuns são realizadas (inserção, pesquisa e remoção de registros).
Pesquisa Sequencial
A pesquisa sequencial é conhecida como o método mais simples de buscar registros, utilizada para buscas em memória interna. Começando do primeiro registro, busca-se sequencialmente até encontrar a chave desejada comparando os elementos. Os registros ficarão armazenados em um vetor (array). Ao inserir um novo registro, este é adicionado ao final do vetor; ao remover, o registro é localizado, removido e o último item do vetor é colocado em seu lugar.
Ao ser efetuada, a pesquisa retorna o índice do registro que contém a chave solicitada (x), caso não seja encontrada, o valor retornado é -1. Seu tempo de execução aumenta de acordo com o tamanho do vetor. Um vetor possui uma quantidade de elementos (n), no melhor cenário o registro desejado será encontrado na primeira tentativa, se não existir ou estiver na última posição, precisará de n comparações.
A busca sequencial não é indicada para tabelas onde há mais de um registro que possui a mesma chave, pois retornará o primeiro registro encontrado somente, pode ser utilizada de forma simples ou com a ajuda de um sentinela.
Exemplo de Busca Sequencial Simples
A seguir um exemplo de um algoritmo de busca sequencial simples:
var vetnum: vetor[0..3] de inteiro; elemento, posicao, indice: inteiro; achou: lógico; inicio vetnum <- [30, 20, 10, 8]; tamanho <- vetnum.tamanho; escreva 'Digite o elemento que deseja encontrar'; leia elemento; achou <- falso; indice <- 0; enquanto indice < tamanho e achou = falso se elemento = vetnum[indice] achou <- verdadeiro; posicao <- indice + 1; fimse indice <- indice + 1; fimenquanto se achou = verdadeiro escreva 'Elemento encontrado na ' + posicao + 'ª do vetor.'; senao escreva 'O elemento não foi encontrado.'; fimse end |
Este algoritmo recebe do usuário a escolha do elemento que será pesquisado e busca o valor no vetor, índice a índice. Quando encontra, atribui verdadeiro para a variável de tipo lógico achou.
Foi utilizado um vetor com 4 posições e declaradas três variáveis de tipo inteiro: elemento (o valor que será recebido do usuário), posição (posição que o elemento se encontra no vetor) e o índice (que será o contador das posições). Foi declarada também a variável tamanho que receberá o tamanho do vetor.
A variável achou será iniciada com valor falso e a variável índice com valor 0, afinal não foi efetuada nenhuma pesquisa ainda. O valor digitado pelo usuário é recebido e armazenado na variável elemento.
Em seguida inicia-se um loop enquanto, que irá rodar enquanto o índice for menor que o tamanho do vetor e a variável achou for falsa. Dentro deste loop, temos uma estrutura de decisão se que verifica se o elemento procurado é igual ao elemento que está registrado no índice atual do vetor. Enquanto este elemento não for encontrado, a variável índice recebe +1 para ir para a próxima posição, este loop só terminará quando o valor for encontrado ou então chegar ao fim do vetor.
...