Recherche binaire de structure de données et d'algorithmes

La recherche binaire est un algorithme de recherche rapide avec une complexité d'exécution de Ο (log n). Cet algorithme de recherche fonctionne sur le principe de diviser pour conquérir. Pour que cet algorithme fonctionne correctement, la collecte de données doit être triée.

La recherche binaire recherche un élément particulier en comparant l'élément le plus au milieu de la collection. Si une correspondance se produit, l'index de l'élément est renvoyé. Si l'élément du milieu est supérieur à l'élément, l'élément est recherché dans le sous-tableau à gauche de l'élément du milieu. Sinon, l'élément est recherché dans le sous-tableau à droite de l'élément du milieu. Ce processus se poursuit également sur le sous-tableau jusqu'à ce que la taille du sous-tableau soit réduite à zéro.

Comment fonctionne la recherche binaire?

Pour qu'une recherche binaire fonctionne, il est obligatoire que le tableau cible soit trié. Nous apprendrons le processus de recherche binaire avec un exemple pictural. Ce qui suit est notre tableau trié et supposons que nous devons rechercher l'emplacement de la valeur 31 en utilisant la recherche binaire.

Tout d'abord, nous allons déterminer la moitié du tableau en utilisant cette formule -

mid = low + (high - low) / 2

Le voici, 0 + (9 - 0) / 2 = 4 (valeur entière de 4,5). Donc, 4 est le milieu du tableau.

Maintenant, nous comparons la valeur stockée à l'emplacement 4, avec la valeur recherchée, c'est-à-dire 31. Nous constatons que la valeur à l'emplacement 4 est 27, ce qui n'est pas une correspondance. Comme la valeur est supérieure à 27 et que nous avons un tableau trié, nous savons également que la valeur cible doit être dans la partie supérieure du tableau.

Nous changeons notre bas en mid + 1 et retrouvons la nouvelle valeur moyenne.

low = mid + 1
mid = low + (high - low) / 2

Notre nouveau milieu a maintenant 7 ans. Nous comparons la valeur stockée à l'emplacement 7 avec notre valeur cible 31.

La valeur stockée à l'emplacement 7 n'est pas une correspondance, c'est plutôt plus que ce que nous recherchons. Ainsi, la valeur doit être dans la partie inférieure de cet emplacement.

Par conséquent, nous calculons à nouveau le milieu. Cette fois, il est 5.

Nous comparons la valeur stockée à l'emplacement 5 avec notre valeur cible. Nous trouvons que c'est un match.

Nous concluons que la valeur cible 31 est stockée à l'emplacement 5.

La recherche binaire divise par deux les éléments interrogeables et réduit ainsi le nombre de comparaisons à effectuer à un nombre très réduit.

Pseudocode

Le pseudocode des algorithmes de recherche binaire devrait ressembler à ceci -

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Pour en savoir plus sur l'implémentation de la recherche binaire à l'aide de array en langage de programmation C, veuillez cliquer ici .