L'un des algorithmes les plus fondamentaux en informatique est l'algorithme de recherche binaire. Vous pouvez implémenter la recherche binaire à l'aide de deux méthodes: la méthode itérative et la méthode récursive. Alors que les deux méthodes ont la même complexité temporelle, la méthode itérative est beaucoup plus efficace en termes de complexité spatiale.

La méthode itérative a une complexité spatiale de O(1) comparé à O(connexion) produit par la méthode récursive. Alors, comment pouvez-vous implémenter l'algorithme de recherche binaire à l'aide de la méthode itérative en C, C++ et Python ?

Qu'est-ce que la recherche binaire ?

La recherche binaire, également connue sous le nom de recherche à demi-intervalle, recherche logarithmique ou hachage binaire, est un algorithme qui recherche et renvoie la position d'un élément dans un tableau trié. L'élément de recherche est comparé à l'élément du milieu. En prenant la moyenne des limites inférieure et supérieure, vous pouvez trouver les éléments intermédiaires.

instagram viewer

Si l'élément de recherche est supérieur à l'élément du milieu, cela signifie que tous les éléments du côté gauche sont plus petits que l'élément de recherche. Ainsi, le contrôle se déplace vers le côté droit du tableau (si le tableau est dans l'ordre croissant) en augmentant la limite inférieure jusqu'à la position suivante de l'élément du milieu.

De même, si l'élément de recherche est plus petit que l'élément du milieu, cela signifie que tous les éléments du côté droit sont supérieurs à l'élément de recherche. Ainsi, le contrôle se déplace vers la partie gauche du tableau en modifiant la limite supérieure à la position précédente de l'élément du milieu.

Cela réduit considérablement le nombre de comparaisons par rapport à implémentation de la recherche linéaire où le nombre de comparaisons est égal au nombre d'éléments dans le pire des cas. Cette méthode s'avère très utile pour trouver des numéros dans un annuaire ou des mots dans un dictionnaire.

Voici une représentation schématique de la Algorithme de recherche binaire:

Recherche binaire à l'aide de C

Suivez ces étapes pour implémenter la recherche binaire à l'aide de C :

L'intégralité du code source du programme de recherche binaire utilisant C, C++, Java et Python est présent dans ce Référentiel GitHub.

Le programme définit une fonction, recherche binaire(), qui renvoie soit l'indice de la valeur trouvée, soit -1 s'il n'est pas présent :

#inclure <stdio.h>
entierrecherche binaire(entier arr[], entier arr_size, entier numéro_recherche){
/*... */
}

La fonction fonctionne en réduisant de manière itérative l'espace de recherche. Étant donné que la recherche binaire fonctionne sur des tableaux triés, vous pouvez calculer le milieu, ce qui n'aurait pas de sens autrement. Vous pouvez soit demander à l'utilisateur un tableau trié, soit utiliser des algorithmes de tri tels que le tri à bulles ou par sélection.

Le faible et haut les variables stockent les index qui représentent les limites de l'espace de recherche courant. milieu stocke l'index au milieu :

entier bas = 0, haut = arr_size - 1, mi ;

Le principal alors que() boucle réduira l'espace de recherche. Si la valeur de l'index bas devient supérieure à l'index haut, alors l'espace de recherche a été épuisé, donc la valeur ne peut pas être présente.

alors que (faible <= élevé) {
/* continue... [1] */
 }
retour-1;

Après avoir mis à jour le point médian au début de la boucle, il y a trois résultats possibles :

  1. Si la valeur au milieu est celle que nous recherchons, renvoyez cet index.
  2. Si la valeur médiane est supérieure à celle que nous recherchons, réduisez le haut.
  3. Si la valeur médiane est inférieure, augmentez le bas. 
/* [1] ...suite */
 moyen = (bas + (élevé - bas)) / 2 ;
if (arr[mid] == search_number)
retour milieu;
autresi (arr[mid] > search_number)
 élevé = moyen - 1 ;
autre
 bas = moyen + 1 ;

Testez la fonction avec l'entrée de l'utilisateur. Utiliser scanf() pour obtenir une entrée de la ligne de commande, y compris la taille du tableau, son contenu et un nombre à rechercher :

entierprincipal(){
entier arr[100], je, arr_size, search_number ;
 printf("Entrez le nombre d'éléments: ");
 scanf("%d", &arr_size);
 printf("Veuillez saisir des chiffres: ");
pour (i = 0; je < arr_size; je++) {
 scanf("%d", &arr[i]);
 }


printf("Entrez le numéro à rechercher: ");
 scanf("%d", &numéro_recherche );


i = binarySearch (arr, arr_size, search_number);


si (i==-1)
 printf("Numéro non présent");
autre
 printf("Le numéro est présent à la position %d", je + 1);
retour0;
}

Si vous trouvez le numéro, affichez sa position ou son index, sinon un message indiquant que le numéro n'est pas présent.

Recherche binaire en C++

Vous pouvez convertir le programme C en programme C++ en important le Flux de sortie d'entrée et utiliser l'espace de noms std pour éviter de le répéter plusieurs fois tout au long du programme.

#inclure <iostream>
en utilisant espace de nomsstd;

Utiliser écoute avec opérateur d'extraction << au lieu de printf() et cin avec opérateur d'insertion >> au lieu de scanf() et votre programme C++ est prêt.

printf("Entrez le nombre d'éléments: ");
écoute <<"Entrez le nombre d'éléments: ";
scanf("%d", &arr_size);
cin >> arr_size ;

Recherche binaire à l'aide de Python

Comme Python n'a pas de support intégré pour les tableaux, utilisez des listes. Définir une fonction, recherche binaire(), qui accepte trois paramètres, la liste, sa taille et un nombre à rechercher :

définitivementrecherche binaire(arr, arr_size, search_number):
 bas = 0
 haut = arr_size - 1
alors que faible <= élevé :
 moyen = bas + (haut-bas)//2
 if arr[mid] == search_number :
retour milieu
elif arr[mid] > search_number :
 élevé = moyen - 1
autre:
 bas = moyen + 1
retour-1

Initialiser deux variables, faible et haut, pour servir de limite inférieure et supérieure de la liste. Semblable à l'implémentation C, utilisez un alors que boucle qui réduit l'espace de recherche. Initialiser milieu pour stocker la valeur médiane de la liste. Python fournit l'opérateur de division de plancher (//) qui fournit le plus grand nombre entier possible.

Effectuez les comparaisons et réduisez l'espace de recherche jusqu'à ce que la valeur médiane soit égale au numéro de recherche. Si le numéro de recherche n'est pas présent, la commande retournera -1.

arr_size = int (entrée("Entrez le nombre d'éléments: "))
arr=[]
imprimer("Veuillez saisir des chiffres: ", fin="")
pour i dans la plage (0,arr_size):
 arr.append(entier(saisir()))
numéro_recherche = int (entrée("Entrez le numéro à rechercher: "))
result = binarySearch (arr, arr_size, search_number)
si résultat == -1 :
 imprimer("Numéro non présent")
autre:
 print("Nombre est présent à la position ", (résultat + 1))

Testez la fonction avec l'entrée de l'utilisateur. Utiliser saisir() pour obtenir la taille de la liste, son contenu et un nombre à rechercher. Utiliser entier() pour transtyper l'entrée de chaîne acceptée par Python par défaut en un entier. Pour ajouter des numéros à la liste, utilisez les ajouter() fonction.

Appel recherche binaire() et passer les arguments. Si vous trouvez le numéro, affichez sa position ou son index, sinon un message indiquant que le numéro n'est pas présent.

Sortie de l'algorithme de recherche binaire

Voici la sortie de l'algorithme de recherche binaire lorsque l'élément est présent dans le tableau :

Voici la sortie de l'algorithme de recherche binaire lorsque l'élément n'est pas présent dans le tableau :

Apprenez les structures de données fondamentales et les algorithmes

La recherche est l'un des premiers algorithmes que vous apprenez et est souvent demandée lors de concours de codage, de stages et d'entretiens. Certains autres algorithmes que vous devriez apprendre sont les algorithmes de tri, de hachage, de programmation dynamique, de correspondance de chaînes et de test de primalité.

De plus, il est essentiel de comprendre la complexité temporelle et spatiale des algorithmes. Ils sont l'un des concepts les plus cruciaux en informatique pour déterminer l'efficacité de tout algorithme. Avec une connaissance des structures de données et des algorithmes, vous êtes tenu de construire les meilleurs programmes.