Programação orientada a objetos

6. TÉCNICAS DE BUSCA E ORDENAÇÃO EM CADEIAS

Até .....

6.1 Técnicas de Busca em Cadeias

Técnicas de Busca em Cadeias:

Existem 2 técnicas comumente utilizadas para se buscar um determinado elemento dentro de uma cadeia (vetor) de elementos:

1. Busca Seqüencial: Efetua-se uma varredura no vetor, verificando campo a campo os elementos, até encontrar o elemento desejado ou até que todo o vetor já tenha sido varrido. Aplicado em vetores desordenados ou de ordem desconhecida.

program Busca_Sequencial ; var x, n, i: integer; a: array[1..200]of integer ; achou: boolean ; begin read (n) ; {* lendo o tamanho do vetor *} for i := 1 to n do {* lendo o vetor *} read (A[i]) ; read (x) ; (* lendo o elemento a ser procurado dentro do vetor *) i := 0 ; achou := false ; repeat i := i + 1 ; achou := x = a[i] ; until achou or (i = n) ; if achou then write (´Encontrado na Posição ´, i ) else write (´Não Encontrado !!!´); end.

2. Busca Binária: Utilizada somente para cadeias ordenadas, da seguinte forma: Escolhe-se um elemento em uma posição média do vetor, dividindo assim, o vetor em 2 segmentos. Então, efetua-se uma comparação do elemento procurado com este elemento central, para saber se o elemento procurado poderia estar localizado no primeiro segmento, no segundo segmento ou se seria o próprio elemento central. Se não for o elemento central, considera-se o segmento escolhido como sendo o vetor a ser novamente analisado, mas agora com apenas metade dos elementos. Então, repete-se o processo, escolhendo um elemento central deste vetor e comparando-o com o elemento procurado, e assim por diante, até encontrar o elemento ou não existir mais campos a serem comparados.

Para implementarmos esta técnica de busca, utilizamos duas variáveis que marcam o início e o fim do segmento a ser analisado, chamadas inicio e fim, que inicialmente