Slides Algoritmos de busca

Pesquisa em memória primária

Estudo dos algoritmos de busca sequencial e binária

Prof. Daniel Gomes Soares

Estruturas de Dados

1

Introdução
Existe uma variedade enorme de métodos de pesquisa.
A escolha do método de pesquisa mais adequado a determinada aplicação depende principalmente:

I) Da quantidade de dados envolvidos
II) De o arquivo estar sujeito a inserções e retiradas frequentes. Estruturas de Dados

2

Pesquisa sequencial
Pode ser executado em um vetor ordenado e em um não ordenado.
• Em um vetor não ordenado, será buscado o número até que seja encontrado ou até se chegar ao final do vetor. • Em um vetor ordenado, será buscado o número até que seja encontrado e enquanto for maior que o número do vetor.

Estruturas de Dados

3

Pesquisa sequencial
Vetor não ordenado

Estruturas de Dados

Vetor ordenado

4

Pesquisa Binária
O vetor com os dados é dividido ao meio e o número do meio é comparado com o número procurado. Se iguais, a busca termina; se menor que o do meio, a busca será realizada no vetor à esquerda. Se maior que o do meio, será realizada no vetor à direita.

Estruturas de Dados

5

Pesquisa Binária - Pseudocódigo
1.
2.
3.
4.
5.
6.
7.

Seja min = 0 e max = n-1.
Se max < min, então pare: valorProcurado não está presente em array.
Retorne -1.
Calcule meio como a média de max e min, arredondado para baixo(de modo que ele seja um número inteiro).
Se array[meio] é igual a valorProcurado, então pare. Você o encontrou!
Retorne meio.
Se a suposição tiver sido baixa demais, ou seja, array[meio] < valorProcurado, então faça min = meio + 1.
Caso contrário, a suposição foi alta demais. Faça max = meio - 1.
Volte para a etapa 2.

Estruturas de Dados

6

Pesquisa Binária

Estruturas de Dados

7

Estruturas de Dados

8

Estruturas de Dados

9

Estruturas de Dados

10

Estruturas de Dados

11