Engª Mecânica, Engª Manutenção Industrial e Engª Mecânica de Transportes

Introdução à Computação e Métodos Numéricos

Algoritmo de pesquisa binária. Este algoritmo assume que o vector onde vamos pesquisar o valor está ordenado.

Existem 2 variáveis (esq e dir) que têm os limites inferior e superior do intervalo onde se encontra o valor a procurar. Esse intervalo vai sendo sucessivamente dividido a meio, sendo eliminada a parte esquerda se o valor a procurar for superior ao valor do vector no ponto médio, ou então sendo eliminada a parte direita se o valor a procurar for inferior ao valor do vector nesse mesmo ponto médio.

O ciclo repete-se até achar o valor ou então até não ser possível dividir de novo o intervalo (significa que o valor não existe).

Program PesquisaBinaria;

Const n=6;

Var i, esq, dir, m, x:Integer;

v:Array[1..n] Of Integer;

fim:Boolean;

Begin

{Armazenar n elementos inteiros num vector ordenado}

For i:=1 To n Do Begin

Write('V[',i,']= ');

ReadLn(v[i]);

End;

{Qual o valor a procurar}

Write('Valor= ');

ReadLn(x);

{}

Fim:=False;

esq:=1;

dir:=n;

Repeat

m:=(esq+dir) Div 2;

If v[m]<x Then esq:=m

Else If v[m]>x Then dir:=m

Else Fim:=True;

Until Fim Or (dir-esq=1);

If v[esq]=x Then WriteLn(x,' encontra-se na ',esq,'ª posição')

Else If v[dir]=x Then WriteLn(x,' encontra-se na ',dir,'ª posição')

Else If v[m]=x Then WriteLn(x,' encontra-se na ',m,'ª posição')

Else WriteLn(x,' não se encontra no vector');

End.

Comentários para: Nuno Castro