Algoritmo de Busca

O problema de localizar um elemento em uma lista ordenada aparece em muitos contextos. Por exemplo, um programa que verifica a ortografia de uma palavra procura-a em um dicionário, que é apenas uma lista ordenada de palavra. Problemas desse tipo são chamados de problema de busca.

O problema de busca geral pode ser assim descrito: localize um elemento x em uma lista de elementos distintos a1, a2... an, ou determine que ele não está na lista. A solução para esse problema de busca é a localização do termo na lista que é igual a x (ou seja, i é a solução se x = a1) e é 0 se x não estiver na lista. O primeiro algoritmo que apresentamos é chamado de algoritmo de busca linear ou busca sequencial.

Exemplo 1:

Procedimento busca linear (x: número inteiro, a1, a2... an: inteiros distintos).

i =1

While (i <= n e x ≠ a2)

             i = i+1

If i <= n então localização = 1

Else localização = 0

(Localização é subscrito igual a x, ou 0, se x não for encontrado).

BUSCA BINÁRIA

A busca binária é outro algoritmo de busca que pode ser usado quando a lista tem termos que aparecem em ordem crescente de tamanho, por exemplo, se os termos forem números, eles estão listados do menor para o maior, se forem palavras estão listadas em ordem alfabética. Esse algoritmo funciona a partir de comparação do elemento localizado no meio da lista, a lista é dividida em duas. A busca continua pela restrição da busca da sublista apropriada com base na comparação do elemento que será colocado com termo central.

Exemplo 2:

Encontre o número 19 na lista

1 2 3 4 5 6 7 8 10 12 13 15 16 18 19 20 22

Primeiro, divida a lista que tem 16 termos em duas listas menores de 8 termos, ou seja,

1 2 3 4 5 6 7 8 10                                                   12 13 15 16 18 19 20 22

Então, compare 19 com o maior termo da primeira lista, como 10 < 19, a procura pelo 19 pode ser restrita a segunda lista, então, divida a segunda lista em duas

12 13 15 16                                                            18 19 20 22

Portanto, como o 16 < 19, realizamos o mesmo processo:

18 19                                                                       20 22

Como 19 não é maior que o maior termo da primeira dessas duas listas, que também é 19, a busca é restrita a primeira lista:

18                                                                            19

Depois essa lista de dois termos é dividida em duas listas com um termo em cada, como 18 < 19, localizamos o número 19 que é localizado como o 14º termo na lista original.