Step-by-step operation of binary search algorithm

Question

I’m trying to solve the following problem:

Create a graphical representation by illustrating ALL steps (where the start, middle and end) of the search for the value element 57 of the following list:

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

I’m doing it, but I don’t know how to continue!

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

1. In the initial interval, I have início the 12, in the meio the 39 and in the fim the 74. The calculation to locate the central element was this: (início + fim) / 2, where:
   • início = 0
   • fim = 12
   • Therefore, meio = (0 + 12) / 2= 12 / 2 = 6, then 6 is the position of the vector’s central element.
2. I divided the list again from the posterior element to the one in the middle, because the sought is larger than the one in the middle, and now item 57 is início.

How to continue? Where will the next medium be?

Answer 1

Pedro Rangel’s approach to representing binary search is to partition the list into sub-lists where the index is redefined. It’s pretty intuitive the way he played it.

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 limits. At each iteration, it is as if these limits were being "flattened" or "cut in half".

Let’s see...

Step 1

Seeking 57. Middle calculation: (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, therefore, move the início for the element to right of meio previous, in position 7.

Also move the meio for 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, therefore, move the início for the element to left of meio previous, in position 8.

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

In the case, início and meio will both be in position 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

Step 4

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

Answer 2

To solve your problem:
I created a graphic representation, illustrating ALL steps (where the start, middle and end) of the search for the value element 57 of 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 down below:

Answer 3

Cool, I think I’ve never heard of it. So I got interested and made a script in PHP to perform this search.

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

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

Exit:

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

Answer 4

Excellent response from @utluiz.

Complementing the reply of @kaduAmaral I made a function to help in the resolution/understanding.

<?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));

I used as an example a Python script from the book "Understanding Algorithms" by Aditya Y. Bhargava published in Brazil by Novatec.