Programme C pour la recherche binaire (récursive et itérative)

L'algorithme de recherche binaire est un algorithme basé sur un mécanisme de comparaison et de segmentation. L'algorithme de recherche binaire est également appelé recherche à demi-marge, recherche logarithmique ou recherche binaire. Algorithme de recherche binaire pour trouver la position d'une valeur cible dans un tableau trié. Il compare la valeur cible à l'élément central du tableau. Si l'élément est égal à l'élément cible, l'algorithme renvoie l'indice de l'élément trouvé. S'ils ne sont pas égaux, l'algorithme de recherche utilise la moitié du tableau, en fonction de la comparaison des valeurs, l'algorithme utilise la première moitié (lorsque la valeur est inférieure au milieu) et la seconde moitié (lorsque la valeur est inférieure à le milieu) et la seconde moitié (lorsque la valeur est supérieure au milieu) . Faites de même avec la moitié suivante du tableau.

Input:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55
Output:
55 at Index = 8

Explication

Pour notre tableau -

nous comparerons 55 avec l'élément du milieu du tableau 18 qui est inférieur à 55 donc nous utiliserons la seconde moitié du tableau qui est le tableau {24, 45, 55, 99} , le milieu est également 55. Utilisez-le pour vérifier la valeur de l'élément de recherche. Et la valeur correspondante, nous renverrons alors l'index de la valeur comme 8.

Si l'élément de recherche est inférieur au milieu, alors nous utiliserons la première moitié et continuerons jusqu'à ce que l'élément soit trouvé au milieu du tableau.

Afin d'implémenter la recherche binaire, nous pouvons écrire du code de deux manières. Ces deux méthodes diffèrent uniquement de la manière dont nous appelons la fonction qui vérifie l'élément de recherche binaire. Ce sont :

• Utiliser l'itération - Cela signifie utiliser une boucle à l'intérieur d'une fonction pour vérifier l'égalité des éléments intermédiaires. < /p>

• Utilisation Dans cette méthode, la fonction s'appelle encore et encore avec un ensemble de valeurs différent.

Exemple

#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
   int A[] = {0,12,6,12,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d </p><p>",n,iterativeBsearch(A,10,n));
   return 0;
}
int iterativeBsearch(int A[], int size, int element) {
   int start = 0;
   int end = size-1;
   while(start<=end) {
      int mid = (start+end)/2;
      if( A[mid] == element) {
         return mid;
      } else if( element < A[mid] ) {
         end = mid-1;
      } else {
         start = mid+1;
      }
   }
   return -1;
}

Sortie

55 is found at Index 8

Exemple

#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
   if(start>end) return -1;
      int mid = (start+end)/2;
   if( A[mid] == element ) return mid;
   else if( element < A[mid] )
      RecursiveBsearch(A, start, mid-1, element);
   else
      RecursiveBsearch(A, mid+1, end, element);
}
int main() {
   int A[] = {0,2,6,11,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d </p><p>",n,RecursiveBsearch(A,0,9,n));
   return 0;
}

Sortie

55 is found at Index 8

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!