Estrutura Aula 14

Busca (Aula 14)
Nesta seção serão estudadas estratégias de busca. Conceitualmente, busca consiste em pesquisar uma grande quantidade de informação para que um determinado dado seja encontrado. Em sistemas de computação esta tarefa é comumente realizada (por exemplo, em sistemas de bancos de dados) e interfere diretamente na performance do sistema.
Conceitos Iniciais
Uma tabela ou arquivo consiste em um conjunto de elementos chamados registros. Associada a cada registro está uma chave que distingue um determinado registro dos demais. Normalmente existe um determinado conjunto de chaves únicas. Tal conjunto é chamado chave primária. Um exemplo disso é um vetor. Se considerarmos cada elemento do vetor um elemento do conjunto a ser pesquisado, o índice do array é a chave primária desse conjunto. Porém, uma aplicação pode utilizar outros campos como chave, e tais valores podem não ser únicos. Tais chaves podem ser chamadas de chaves secundárias. Uma tabela pode estar armazenada, basicamente de duas formas:
Completamente disponível em memória: diz-se que um algoritmo que realiza busca nessas condições realiza busca interna;
Parte armazenada em memória e parte armazenada em um meio secundário de armazenamento: diz-se que um algoritmo que realiza busca nessas condições realiza busca externa.
A forma mais comum de busca realizada é a busca interna, porém, algumas formas de busca externa também serão estudadas.
Busca Seqüencial
A forma mais comum de busca é a busca seqüencial. Esta estratégica de busca pode ser aplicada tanto sobre uma tabela quanto para uma lista encadeada. Ela consiste em percorrer todos os elementos armazenados a partir do primeiro, até que o registro cuja chave a seja encontrada ou o final do conjunto seja obtido (busca falhou). Dada uma array v de tamanho n, e uma função k(i) que retorna a chave de um determinado registro i, o algoritmo de busca seqüencial seria o seguinte:

for(int i = 0; i < n; i++) if(a == k(i)) return i; return –1;