Explication des algorithmes de recherche binaire à l'aide de C ++

La recherche binaire est l'un de ces algorithmes que vous rencontrerez à chaque (bon) cours d'introduction à l'informatique. C'est un algorithme efficace pour trouver un élément dans une liste ordonnée . Pour les besoins de cet exemple, nous supposerons simplement qu'il s'agit d'un tableau.

Les objectifs de la recherche binaire sont les suivants:

  • être capable de supprimer la moitié du tableau à chaque itération
  • minimiser le nombre d'éléments que nous devons traverser
  • laissez-nous une valeur finale

Prenons par exemple le tableau d'entiers suivant:

int array[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 };

Disons que nous essayons de trouver la valeur d'index du nombre 7 dans ce tableau. Il y a 17 éléments au total et les valeurs d'index vont de 0 à 16.

Nous pouvons voir que la valeur d'index de 7 est 4, car c'est le cinquième élément du tableau.

Mais quel serait le meilleur moyen pour l'ordinateur de trouver la valeur d'index du nombre recherché?

Tout d'abord, nous stockons les valeurs minet max, telles que 0et 16.

int min = 0;int max = 16;

Nous devons maintenant faire une estimation. La chose la plus intelligente à faire serait de deviner une valeur d'index au milieu du tableau.

Avec la valeur d'index 0 à 16 dans ce tableau, la valeur d'index intermédiaire de ce tableau serait 8. Cela contient le nombre 14.

// This will round down if the quotient is not an integer

int guess = (min + max) / 2;

Notre estimation est maintenant égale à 8, qui est 14 dans le tableau, car array[8]est égale à 14.

Si le nombre que nous recherchions était de 14, nous aurions terminé!

Puisque ce n'est pas le cas, nous allons maintenant supprimer la moitié du tableau. Ce sont tous les nombres après 14, ou valeur d'index 8, puisque nous savons que 14 est supérieur à 7 et que notre estimation est trop élevée.

Après la première itération, notre recherche est maintenant dans: 1, 3, 4, 6, 7, 8, 10, 13

Nous n'avons pas à deviner dans la dernière moitié du tableau d'origine, car nous savons que toutes ces valeurs sont trop grandes. C'est pourquoi il est important d'appliquer la recherche binaire à une liste ordonnée .

Étant donné que notre estimation initiale de 14 était supérieure à 7, nous la diminuons maintenant de 1 et la stockons dans max:

max = guess - 1; // max is now equal to 7, which is 13 in the array

Maintenant, la recherche ressemble à ceci:

 1, 3, 4, 6, 7, 8, 10, 13
min = 0max = 7guess = 3 

Parce que notre estimation était trop basse, nous supprimons la moitié inférieure du tableau en augmentant le min, contrairement à ce que nous avons fait précédemment pour max:

min = guess + 1; // min is now 4

À la prochaine itération, il nous reste:

 7, 8, 10, 13min = 4max = 7guess = 5

Puisque la valeur d'index 5 renvoie 8, nous sommes maintenant un au-dessus de notre objectif. Nous répétons le processus à nouveau, et il nous reste:

 7min = 4max = 4guess = 4

Et il ne nous reste qu'une seule valeur, 4, comme indice du nombre cible que nous recherchions, qui était 7.

Le but de la recherche binaire est de se débarrasser de la moitié du tableau à chaque itération. Nous ne travaillons donc que sur les valeurs sur lesquelles il est logique de continuer à deviner.

Le pseudo-code de cet algorithme ressemblerait à ceci:

  1. Let min = 0, et let max = nnest la valeur d'index la plus élevée possible
  2. Trouvez la moyenne de minet max, arrondissez vers le bas pour que ce soit un entier. C'est notreguess
  3. Si nous avons deviné le nombre, arrêtez, nous l'avons!
  4. Si guessest trop bas, définir minégal à un de plus queguess
  5. Si guessest trop élevé, définir maxégal à un de moins queguess
  6. Revenez à la deuxième étape.

Voici une solution, écrite en C ++: