Algoritmo de Pesquisa Binária

Para a implementação da pesquisa binária num vector V de N valores inteiros ordenados de uma forma crescente, adopta-se o seguinte algoritmo:

Função  Pesquisa_Binária(V,N,X)
{   
  1.Inicializar a  pesquisa e inicializar variáveis
        ini=1;
        fim=N;
2. Percorrer o vector para encontrar o elemento
      Do While   ini <= fim
                meio= INT((ini+fim)/2)

                 if  X <V[meio]
                    then fim= meio-1
                 else   if x> V[meio]
                        then ini= meio+1;
                                 else   write("elemento encontrado")
                                       return (meio)
3. Percorreu todo o vector e não encontrou o elemento
  return (0)

Pesquisa Binária

Pesquisa Binária

A estratégia a adoptar neste algoritmo passa por comparar o elemento que procuramos com o valor do elemento armazenado no meio do vector.

* Se esse elemento for menor que o elemento do meio, então conclui-se que, se o elemento estiver presente no  vector , ele estará na primeira parte do mesmo.

* Se o elemento a pesquisar for maior, então estará na segunda parte do vector. Logicamente que se for igual, estará encontrado o elemento do vector e a pesquisa ficará concluída.

*  Se o elemento estiver estiver num das partes do vector, repete-se o procedimento considerando apenas a parte que restou e compara-se o elemento a procurar com o elemento de armazenado no meio dessa parte.

Em suma:
Há 3 tipos de comparações entre o elemento X a pesquisar e o valor v[i] que representa o valor posicionado no meio da estrutura de dados:


     -> Se o X= V[i] então a pesquisa é bem sucedida. A pesquisa termina.

     -> Se o X <V[i] então a pesquisa deve prosseguir na sub-lista dos elementos que procedem V[i], ou seja na primeira metade da lista.

     -> Se X> V[i] então a pesquisa deve prosseguir na sub-lista dos elementos que sucedem V[i], ou seja na segunda metade da lista