Algoritmos de Pesquisa Sequencial e Binária

A capacidade de armazenar informações foi um passo decisivo na evolução da ciência da computação e para o nível generalizado de utilização do computador. Com isso, a capacidade de recuperar informações, para posterior processamento, assume papel de suma importância na utilização cotidiana do computador, existindo para isto inúmeros exemplos, como: recuperação de dados de dados de transações bancárias de um cliente através de um número de conta, no cadastro de cliente/operações de um banco. Portanto, algoritmos de pesquisa devem ser projetados de forma a garantir a confiabilidade e eficiência exigidas pela importância das aplicações existentes.

A pesquisa de dados pode ser efetuada tanto em unidades de memória secundárias (disco rígido, disquetes, fita), quanto na memória principal do computador. 

Pesquisa Sequencial

O método mais simples de determinar a presença, ou não, de um elemento numa sequência, é percorrê-la a partir do seu início, efetuando comparações, até que o elemento seja encontrado ou o fim da sequência seja alcançado. Este método é chamado de pesquisa sequencial.

Dados :

vetor de n elementos (n conhecido) 

elemento a ser pesquisado no vetor

Resultado: 

Se o elemento existe, mostra-se a sua posição ou o total de ocorrências deste no vetor.

Se o elemento não existe, mostra-se uma mensagem de falha.

As considerações que podem ser feitas sobre os dados de entrada (vetor), são do tipo: o vetor esta ou não ordenado; o elemento ocorre uma única vez (pesquisa única) ou repetidas vezes no vetor (pesquisa única). 

Isso acarreta os seguintes tipos de pesquisa:

a. Desordenada Única

b. Desordenação Múltipla

c. Ordenada Única

d. Ordenada Múltipla

Pesquisa Binária

O método de pesquisa sequencial é fácil de escrever e é razoavelmente eficientes para sequências com poucos elementos. Entretanto, para sequências de tamanho considerável, que ocorrem na maioria das aplicações existentes, a utilização do método torna-se inviável. Uma estratégia interessante e eficiente é utilizada no método de pesquisa binária.

Descrição Geral do Método:

- Definir intervalo inicial (i, f) de busca

- Determinar a posição média do intervalo (m = (i+f) DIV 2)

- Comparar o elemento da posição média (v[m]) com o elemento E:

- Caso sejam iguais então terminou as pesquisa

- Caso contrário definir o novo intervalo de busca

- Aplicar sucessivamente o passo anterior até encontrar E ou não existir mais o intervalo de busca

São aspectos fundamentais do método:

- Vetor de entrada tem que estar ordenado

- Intervalo de busca inicial é (i,f) = (1,n)

- Intervalo de busca, considerado a cada iteração, é definido do seguinte modo:

(i,m-1), se (E < v[m])

(m+1,f), se (E > v[m])

tendo a metade do tamanho do intervalo original

O teste de repetição é (i <= f) e Não Achou

Dados :

vetor de n elementos (n conhecido)

elemento a ser pesquisado no vetor

Resultado

Se o elemento existe, mostra-se a sua posição ou o total de ocorrências deste no vetor.

Se o elemento não existe, mostra-se uma mensagem de falha.