Analisaremos  as  técnicas  de  pesquisa  em  termos  de  tempo  de
execução, ordenação,  restruturação e manutenção das das chaves.

	1) Pesquisa Serial:

	É  a  técnica  mais  fácil  de  ser  implementada de longe e a mais
ineficiente.  Essa  técnica consiste em armazenar as informações em vetores
independentes para cada atributo ou chave, ou armazenar tudo em um vetor de
estruturas.  A  busca  é  feita  percorrendo  todo  o vetor até que a chave
desejada  seja  encontrada  ou até que a comparação seja feita com todas as
posições  do  vetor. A exclusão de registros causa "buracos" no vetor, onde
não  há  informação. Para resolver esse problema, poderíamos deslocar todos
os  registros  posteriores uma posição para trás, mas isso é inviável, pois
esse  processo  levaria  muito  tempo  e tornaria o sistema lento. Por isso
geralmente  marca-se  a  posição  do  registro  excluído de uma maneira que
saibamos  posteriormente  que  aquela  posição  está disponível. Aí, quando
desejarmos  adicionar  um  registro,  procuramos  primeiro  por uma posição
disponível  no  meio  do  vetor, se não houver aí sim usamos uma posição no
final dele.

	2) Ordenação por Frequência:

	Esta  é  uma pequena melhora do processo descrito anteriormente. Só
que  aqui  é guardada em uma tabela a quantidade de vezes que cada registro
foi  consultado.  Os registros são ordenados de forma que os registros mais
consultados ficam no início da tabela e os menos no final. Essa reordenação
obviamente não pode ser realizada constantemente e sim periodicamente e, de
preferência  em  períodos  de  tempo em que o sistema seja menos utilizado.

	3) Pesquisa Sequencial:

	Esta  técnica  consiste  em  armazenar os registros de forma que as
chaves  estejam  ordenadas, seja de forma crescente ou decrescente. No caso
de  ordem  crescente,  a  busca  de uma determinada chave é feita até que o
vetor  acabe,  a  chave  desejada  seja encontrada ou (este é o lance) seja
encontrada  uma chave maior que a chave desejada. Neste caso, a inserção de
registros  é  um  tanto  complicada  pois,  ao  contrário  da ordenação por
frequência,  a  ordenação  das  chaves  um  fator definitivo e que deve ser
constantemente  mantido.  Por isso, cada nova chave inserida na tabela deve
ser  inserida  na  ordem  correta,  mesmo que para isso uma grande parte da
tabela precise ser deslocada.

	4) Pesquisa Binária:

	Aqui a tabela é organizada da mesma forma que no item anterior, por
isso  tem  os  mesmos  problemas  de manutenção da ordem. Mas seu método de
pesquisa  é  bem  mais  eficiente. Começa-se a procurar a chave desejada no
meio  da  tabela. Se a chave encontrada for maior que a chave que queremos,
então  significa  que  a  chave que queremos está (se estiver na tabela) na
primeira  metade  da tabela, senão na segunda. Então tenta-se achar a chave
no  meio da metade que presume-se estar a chave. Repete-se estes passos até
que se encontre a chave ou não existam mais registros.

	definição	MAX	100

	(variável global onde serão guardadas as chaves)
	inteiro: Chaves [0..MAX]

	inteiro: ProcuraChave (inteiro: Chave, Inicio, Fim)
	.	inteiro: Meio
	.	Meio = (Inicio + Fim) / 2
	.
	.	(chave encontrada)
	.	se Chaves [Meio] = Chave então retorna Meio	
	.
	.	(chave não encontrada)
	.	se Inicio = Fim então retorna ERRO
	.
	.	(a chave deve estar na primeira metade)
	.	se Chave < Chaves [Meio] então
	.		retorna ProcuraChave (Chave, Inicio, Meio - 1)
	.
	.	(a chave deve estar na segunda metade)
	.	se Chaves [Meio] < Chave então
	.		retorna ProcuraChave (Chave, Meio + 1, Fim)
	fim

	Pode  implementar,  analogamente  ao  método de pesquisa binária, o
método  de pesquisa ternária, onde cada tabela é dividida em (adivinhem...)
três subtabelas de cada vez. Pesquisas mostram que o ganho de desempenho na
pesquisa ternária com relação à pesquisa binária é desprezível.

	5) Pesquisa Direta:

	Pesquisa  direta  é  quando  utilizamos  a  própria chave (às vezes
ligeiramente  modificada)  como  endereço. Pode ser implementada através de
dois métodos: pesquisa indexada e pesquisa direta transformada.

	5.1) Pesquisa Indexada:

	Neste  tipo  de  pesquisa,  a chave está implícita como endereço do
registro,  portanto  a  tabela  é constituída  apenas por atributos. Como a
chave   define   o   endereço  do  atributo,  podemos  notar  as  seguintes
características:

	(BOM) Não é possível haver colisão;
	(BOM) O  número  médio de comparações para cada pesquisa é  1 (um);
	(RUIM) As  chaves  precisam ser uniformes. Por exemplo, se  estamos
fazendo  um  controle  de  alunos  de  uma  escola e utilizando o número de
matrícula  como  chave  e  esses  números  podem  variar  entre 100 e 5000,
precisamos  criar  uma  tabela  de  4900  registros  (5000 - 100) mesmo que
existam  "buracos" vazios nessa tabela. E isso pode "custar caro". Por isso
geralmente utiliza-se a pesquisa direta transformada.

	5.2) Pesquisa Direta Transformada:

	Pesquisa Direta Transformada é um tipo de pesquisa derivado do tipo
anterior.  A  diferença  que  ela  utiliza alguma fórmula ou algoritmo para
diminuir  o tamanho da tabela. Eu poderia entrar em detalhes de um monte de
discussões  teóricas  e  tal.  Mas  vou  direto  ao ponto: o algoritmo mais
utilizado é o do RESTO.

	Esse  algoritmo  consiste em dividir a chave por um quociente (deve
ser  primo para aumentar a eficiência) e o resto é utilizado como endereço.
Por exemlo, vamos utilizar o quociente 5 para armazenar os seguintes dados:
0, 1, 6, 9, 12, 20, 21, 34.

	Nota-se  que várias chaves geraram o mesmo resto. É lógico que isso
está  diretamente  ligado  ao  número  utilizado  como  quociente.  Mas que
quociente  utilizar?  Bom,  existe um lance chamado FATOR DE CARGA que dado
por: 
		número total de endereços
	FATOR =	------------------------- * 100
		número total de registros 

	Os  matemáticos  e  estatísticos  da vida dizem que esse fator deve
estar  entre  60%  e  70%  para  tabelas fixas e no máximo 80% para tabelas
dinâmicas.   Não   me   pergunte  o  porquê.  Isso  pode  ser  implementado
dinamicamente ou estaticamente.

	5.2.1) Estaticamente:
	

	A  implementação dinâmica deste método consiste em criar uma tabela
cujos  registros  possuem,  além dos atributos, uma chave e um apontador. A
tabela  é dividida em ÁREA PRINCIPAL e ÁREA OVERFLOW. Na área principal são
guardados  os  primeiros  registros  correspondentes a cada valor de resto.
Quando  tentamos  colocar  um novo registro na tabela e ocorre uma colisão,
guardamos  esse novo registro em um espaço vazio da área overflow e fazemos
o  apontador  do  registro  na  área principal apontar para ele e assim por
diante,  de  modo que cada registro aponta para registros cuja chave gera o
mesmo  resto.  Quando queremos retirar um registro, devemos restabelecer as
ligações.  Se  o registro retirado for um da área principal deve-se "puxar"
um  registro  da  área  overflow  de  mesmo  resto  para  ocupar seu lugar.

	As  desvantagens  desse  método  são  as mesmas de todos os métodos
estáticos:  o desperdício de memória, visto que os espaços vazios não podem
ser desalocados, e o tamanho limitado da tabela.

	5.2.2) Dinâmicamente:

	Este  método consiste em nada mais do que criar uma série de listas
encadeadas  (simples  ou  duplas),  cada  uma  correspondente a um valor de
resto. A figura vale mais do que mil palavras:

	Como  todo  método  dinâmico,  este  tem as vantagens de economizar
memória  e  poder ter uma capacidade limitada apenas pela memória física da
máquina.

        Para saber mais...

------>Exemplo de Pesquisa Binária em C
------>Exemplo de Pesquisa Direta Transformada por Resto em C

------>Tabelas
------>Árvores Binárias
------>Listas Encadeadas