15 Algoritmosdebuscaemtabelas Sequencialebinaria 131222165736 Phpapp02

Algoritmos de Busca em Tabelas
MAC122 – Marcilio – Revisado em 13Out12

Algoritmos de Busca em Tabelas
Dentre os vários algoritmos fundamentais, os algoritmos de busca em tabelas estão entre os mais usados.
Considere por exemplo um sistema de banco de dados. As operações de busca e recuperação dos dados são bastante freqüentes. Considere também os programas “buscadores” da Internet (Google, Yahoo, etc.). Em todos eles são usados de alguma maneira os algoritmos básicos de busca em tabelas ou arquivos.
Vamos estudar os métodos internos de busca, isto é, os dados estão em tabelas na memória.
No caso de arquivos há outras variáveis a se considerar. O tempo de acesso aos setores do disco envolve operações mecânicas (movimento do braço e rotação) que podem ser muito mais significativos que o tempo gasto pelo algoritmo. Mas de maneira geral, se um algoritmo é bom para se efetuar busca em tabelas na memória, sempre pode ser adaptado para funcionar também com arquivos.

Busca sequencial
Consiste em varrer uma tabela a procura de um determinado elemento, verificando ao final se o mesmo foi ou não encontrado.
A função busca abaixo, procura elemento igual a x num vetor a de n elementos, devolvendo –1 se não encontrou ou o índice do primeiro elemento igual a x no vetor. É claro que pode haver mais de um elemento igual a x. int busca(int a[], int n, int x){ int i; for (i = 0; i < n; i++)if (a[i] == x) return i;
/* foi até o final e não encontrou */ return -1;
}
Existem várias maneiras de se fazer o algoritmo da busca, por exemplo: int busca(int a[], int n, int x) { int i = 0; while (i < n && a[i] != x) i++;
/* verifica se parou porque chegou ao fim ou encontrou um igual */ if (i == n) return –1; /* chegou ao final */ return i; /* encontrou um igual */
}
Fica como exercício, reescrever a função busca de outras formas, usando o comando for, o comando while e o comando do while da linguagem C.

Busca Sequencial – análise do algoritmo
Considere a função busca do programa acima.