Step-by-step operation of the binary search algorithm

Question

Step-by-step operation of the binary search algorithm

Navigation

#1 by (7 votes)
#2 by (3 votes)
#3 by (3 votes)

3

I'm trying to solve the following problem:

Create a graphical representation, illustrating ALL steps (where the beginning, middle, and end are) of the search for the 57 element from the following list:

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

I'm doing it, but I do not know how to continue!

So far, I've done the following step-by-step tracking:

At the initial interval, I have início 12, and 39 and not meio or 74 . The calculation to locate the central element was this: fim , where:

(início + fim) / 2
início = 0
So% w / o%, then 6 is the position of the center element of the vector.

I split the list again from the element later than the middle element, since the search is greater than the middle one, and now item 57 is fim = 12 .

How to continue? Where will the next medium be?

algoritmo busca

asked by anonymous 30.09.2014 / 17:22

3 answers

Use virtual keyboard to help with security? Why does the order of these scanf's make a difference in the result?

score 7 · Answer 1

Pedro Rangel's approach to representing binary search is to partition the list into sub lists where the index is redefined . It is very intuitive in the way it represented.

There is another approach that I also find intuitive and more practical in some cases. The idea is to represent the limits of the search using a kind of arrow or pointer to demarcate the boundaries. At each iteration, it is as if these boundaries were being "flattened" or "cut" in half.

Let's see ...

Step 1

Searching 57 . Calculation of the mean: (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

Step 2

57 is greater than 39 , so move início to the right element of meio 7 .

Also move the meio to the result of (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

Step 3

57 is less than 63 , so move the início to the left element of meio 8 .

Also move the meio to the result of (7 + 8) / 2 = 7 .

In this case, início and meio will both be in the 7 position.

  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

Step 4

As the value of meio is equal to 57 , we find the result and result of the search is that the element was found at position 7 .

score 3 · Answer 2

To solve your problem:
I created a graphical representation, illustrating ALL the steps (where the beginning, middle and end are) of the search for the value element 57 from the following list, as requested in the question:

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

The figure of Graphic Representation below:

score 3 · Answer 3

Nice, I guess I had never heard of it. So I got interested and did a PHP script to do this search.

I know it is not the answer sought by the author, but I am sharing it for future "researchers."

Follow the code:

$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;

Output:

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