Busca Binária em Matriz Bidimensional em Pascal

Essa postagem vem ajudar a mais um pedido do leitor.

Eu não estou aqui para julgar a necessidade da aplicação, mas acredito que seja apenas para fins educacionais, pois ainda não vi utilidade para isso.

Em primeiro lugar a busca binária parte da premissa para a procura em um vetor ordenado, ou seja, a matriz deverá ser transformada em um vetor.

Há inumeras opções para se desenvolver esse problema, para uma solução melhor só em detalhamento com o vosso professor.

Todo o segredo está em como você armazena os dados para a sua solução.

Programa:

Pesquisa Binária Pascal Matriz 01

Pesquisa Binária Pascal Matriz 02

Código Fonte:

Program Pesquisa_Binaria_em_Matriz_Bidimensional;
Uses CRT;
var
  tabela  : Array [1..5,1..5] of Integer;
  vetor   : Array [1..25] of Integer;
  aux     : Integer;
  i, j, k : Integer;
  inicio  : Integer;
  fim     : Integer;
  meio    : Integer;  {Inicio, Meio e fim do Vetor}
  achou   : Integer;
Begin
  ClrScr;
  Randomize;
  WriteLn ('Matriz');
  WriteLn;
  for i := 1 to 5 do
  Begin
    Write ('[');
    for j := 1 to 5 do
    Begin
      k := Random (10);
      tabela[i,j] := k;
      Write (k:2);
    End;
    WriteLn (' ]');
  End;
  WriteLn;
  WriteLn ('Vetor');
  WriteLn;
  // Pesquisa Binaria se aplica a vetor e ordenado
  // Transformacao em Vetor
  k := 0;
  for i := 1 to 5 do
    for j := 1 to 5 do
    Begin
      k := k + 1;
      vetor[k] := tabela [i,j];
      Write (Vetor[k]: 2);
    End;
  WriteLn;
  // Ordenar o Vetor - Processo SIMPLES
  WriteLn ('Vetor ordenado');
  WriteLn;
  for i := 1 to 24 do
  for j := i+1 to 25 do
  begin
    if vetor [i] > vetor [j] then
    begin
      aux := vetor[i];
      vetor[i] := vetor[j];
      vetor[j] := aux;
    end;
  end;
  for i := 1 to 25 do
  begin
    Write (Vetor[i]:2);
  end;
  WriteLn;
  WriteLn;
  Write ('Qual numero voce deseja encontrar?');
  ReadLn (k);
  // Pesquisa Binaria
  inicio := 1; {Comeca no primeiro elemento}
  fim := 25;   {Termina em 25 que ‚ o £ltimo elemento}
  achou := -1; {caso nÆo ache o final fica -1}
  repeat
    meio := (inicio+fim) div 2;
    if (k = vetor[meio]) then
    begin
      achou := meio;
      inicio := fim+1;  {Interrompe o repeat com o resultado}
    end;
    if (k < vetor[meio]) then
      fim := meio-1;
    if (k > vetor[meio]) then
      inicio := meio+1;
  until (inicio>fim);
  if achou = -1 then
    WriteLn ('NÆo encontrado!')
  else
    WriteLn ('Encontrado na posicao ',achou,
             ' o conteudo no vetor ',vetor[achou]);
  ReadLn;
End.

2 comentários:

  1. O algoritmo converte a matriz em vetor, e só depois disso que realmente aplica a busca binária.
    É um bom código, mas não deixa de ser Busca Binária em Vetor.

    ResponderExcluir
  2. O princípio do estudo em Pascal e descobrir métodos de programação.

    ResponderExcluir