3

Estou tentando resolver o seguinte problema:

Crie uma representação gráfica, ilustrando TODOS os passos (onde fica o início, meio e fim) da busca pelo elemento de valor 57 da seguinte lista:

12,13,15,19,24,28,39,57,59,63,67,69,74

Eu estou fazendo, mas não sei como continuar!

Até o momento, fiz o seguinte rastreamento passo-a-passo:

  1. No intervalo inicial, tenho no início o 12, no meio o 39 e no fim o 74. O cálculo para localizar o elemento central foi esse: (início + fim) / 2, onde:
    • início = 0
    • fim = 12
    • Portanto, meio = (0 + 12) / 2= 12 / 2 = 6, então 6 é a posição do elemento central do vetor.
  2. Dividi a lista novamente a partir do elemento posterior ao do meio, pois o procurado é maior do que o o do meio, sendo que agora o item 57 é o início.

Como continuar? Onde será o próximo meio?

3
  • 1
    @Anderson: Você está tentando implementar uma busca binária? Veja isso: Pesquisa binária - wikipeda... tem vários exemplos Commented 30/09/2014 às 15:51
  • 4
    @Anderson, bem-vindo ao Stack Overflow em Português! Sinto sua dificuldade em tentar fazer perguntas, com alguém que começou hoje aqui na comunidade do SO. Peço desculpas se algo chegou a lhe ofender, mas também peço que entenda que até agora foi difícil de entender exatamente o que você está precisando. Por exemplo, nesta pergunta, você não havia deixado claro qual o algoritmo sendo usado. Pude subentender que você quer representar passo-a-passo uma busca binária, mas veja que isso necessitou de muita atenção na interpretação.
    – utluiz
    Commented 30/09/2014 às 16:05
  • 5
    Tomei a liberdade de editar sua pergunta de forma que ela fique mais clara. Espero que isso o ajude a entender como fazer o mesmo. Espero que continue fazendo perguntas e aproveite a ajuda da comunidade, mas tente ser sempre o mais claro possível, formatar bem o que você escreve usando parágrafos, tópicos e uma linguagem mais formal. Abraço!
    – utluiz
    Commented 30/09/2014 às 16:09

4 Respostas 4

8

A abordagem do Pedro Rangel para representar a busca binária é particionar a lista em sub listas onde o índice é redefinido. É bem intuitiva da forma como ele representou.

Existe outra abordagem que também considero intuitiva e mais prática em alguns casos. A ideia é representar os limites da busca usando uma espécie de seta ou apontador para demarcar os limites. A cada iteração, é como se esses limites fossem sendo "achatados" ou "cortados" pela metade.

Vejamos...

Passo 1

Buscando 57. Cálculo do meio: (0 + 12) / 2 = 6.

  0   1   2   3   4   5   6   7   8   9   10  11  12
  --------------------------------------------------
  12  13  15  19  24  28  39  57  59  63  67  69  74
  |                       |                        |
início                   meio                     fim

Passo 2

57 é maior que 39, portanto, mover o início para o elemento à direita do meio anterior, na posição 7.

Também mover o meio para o resultado de (7 + 12) / 2 = 9.

  0   1   2   3   4   5   6   7   8   9   10  11  12
  --------------------------------------------------
  12  13  15  19  24  28  39  57  59  63  67  69  74
                              |        |           |
                            início    meio        fim

Passo 3

57 é menor que 63, portanto, mover o início para o elemento à esquerda do meio anterior, na posição 8.

Também mover o meio para o resultado de (7 + 8) / 2 = 7.

No caso, início e meio vão estar os dois na posição 7.

  0   1   2   3   4   5   6   7   8   9   10  11  12
  --------------------------------------------------
  12  13  15  19  24  28  39  57  59  63  67  69  74
                              |    |          
                           início  fim
                            meio

Passo 4

Como o valor do meio é igual à 57, encontramos o resultado e o resultado da busca é que o elemento foi encontrado na posição 7.

3

Para solucionar seu problema:
Criei uma representação gráfica, ilustrando TODOS os passos (onde fica o início, meio e fim) da busca pelo elemento de valor 57 da seguinte lista, como pedido na questão:

12,13,15,19,24,28,39,57,59,63,67,69,74

A figura da Representação Gráfica abaixo:

inserir a descrição da imagem aqui

3

Bacana, acho que eu nunca tinha ouvido falar do assunto. Daí me interessei e fiz um script em PHP pra realizar essa busca.

Sei que não é a resposta procurada pelo autor, mas estou compartilhando para futuros "pesquisadores".

Segue o código:

$lista = Array(12,13,15,19,24,28,39,57,59,63,67,69,74);

$el = 69; // Elemento a ser encontrado
$id = 0;
while (is_array($lista)){
   $ini = 0; // Elemento inicial da lista
   $mid = floor(count($lista)/2); // Elemento no meio da lista
   $end = count($lista)-1; // Elemento final da lista

   echo 'INI: '.$lista[$ini].' | ID: '.$ini.PHP_EOL;
   echo 'MID: '.$lista[$mid].' | ID: '.$mid.PHP_EOL;
   echo 'END: '.$lista[$end].' | ID: '.$end.PHP_EOL;
   echo '---------------------------------'.PHP_EOL;

   if ($lista[$mid] < $el){ // Se o elemento estiver na segunda parte da lista
      $tmp = Array();
      for($i = $mid; $i <= $end; $i++)
         $tmp[] = $lista[$i];

      $id += $mid;
      $lista = $tmp;
   } elseif ($lista[$mid] > $el) { // Se o elemento estiver na primeira parte da 
                                   // lista
      $tmp = Array();
      for($i = $ini; $i < $mid; $i++)
         $tmp[] = $lista[$i];

      $lista = $tmp;
   } else { // Elemento no meio da lista
      $id += $mid;
      $lista = PHP_EOL.'Encontrado: '.$lista[$mid].' | ID: '.$id;
   }

   // Checou todos os itens e não encontrou.
   if ($ini == $end && is_array($lista) ) $lista = 'O Item nao existe!'; 

}

echo $lista;

Saída:

INI: 12 | ID: 0
MID: 39 | ID: 6
END: 74 | ID: 12
---------------------------------
INI: 39 | ID: 0
MID: 63 | ID: 3
END: 74 | ID: 6
---------------------------------
INI: 63 | ID: 0
MID: 69 | ID: 2
END: 74 | ID: 3
---------------------------------

Encontrado: 69 | ID: 11
1

Excelente resposta do @utluiz.

Complementando a resposta do @kaduAmaral fiz uma função para ajudar na resolução/entendimento.

<?php

function buscaBinaria(array $lista, int $item) {
    $baixo = 0;
    $alto = count($lista) - 1;


    while ($baixo <= $alto) {
        $meio = ceil(($baixo + $alto) / 2);

        $chute = $lista[$meio];

        if ($chute == $item) {

            return $meio;
        }

        if ($chute > $item) {
            $alto = $meio - 1;
        } else {
            $baixo = $meio + 1;
        }
    }

    return null;
}

$lista = [12,13,15,19,24,28,39,57,59,63,67,69,74];

print_r(buscaBinaria($lista, 57));

Usei como exemplo um script em Python do livro "Entendendo Algoritmos" do Aditya Y. Bhargava publicado no Brasil pela Novatec.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .