Algorithme de recherche binaire avec EXEMPLE

Avant d'apprendre la recherche binaire, apprenons :

Qu'est-ce que la recherche?

La recherche est un utilitaire qui permet à son utilisateur de trouver des documents, des fichiers, des médias ou tout autre type de données contenues dans une base de données. La recherche fonctionne sur le principe simple de faire correspondre les critères avec les enregistrements et de les afficher à l'utilisateur. De cette façon, la fonction de recherche la plus élémentaire fonctionne.

Qu'est-ce que la recherche binaire ?

Une recherche binaire est un type avancé d'algorithme de recherche qui recherche et récupère des données à partir d'une liste triée d'éléments. Son principe de fonctionnement principal consiste à diviser les données de la liste en deux jusqu'à ce que la valeur requise soit localisée et affichée à l'utilisateur dans le résultat de la recherche. La recherche binaire est communément appelée recherche à demi-intervalle ou recherche logarithmique.

Comment fonctionne la recherche binaire ?

La recherche binaire fonctionne de la manière suivante :

• Le processus de recherche démarre en localisant l'élément central du tableau de données trié.
• Après cela, la valeur clé est comparée à l'élément
• Si la valeur clé est plus petite que l'élément du milieu, la recherche analyse les valeurs supérieures jusqu'à l'élément du milieu à des fins de comparaison et de correspondance.
• Dans le cas où la valeur clé est supérieure à l'élément du milieu, la recherche analyse les valeurs inférieures jusqu'à l'élément du milieu à des fins de comparaison et de correspondance.

Exemple de recherche binaire

Prenons l'exemple d'un dictionnaire. Si vous avez besoin de trouver un certain mot, personne ne parcourt chaque mot de manière séquentielle mais localise au hasard les mots les plus proches pour rechercher le mot requis.

L'image ci-dessus illustre ce qui suit :

1. Vous disposez d'un tableau de 10 chiffres et l'élément 59 doit être trouvé.
2. Tous les éléments sont marqués d'un index de 0 à 9. Maintenant, le milieu du tableau est calculé. Pour ce faire, vous prenez les valeurs les plus à gauche et à droite de l'index et vous les divisez par 2. Le résultat est 4.5, mais nous prenons la valeur plancher. Le milieu est donc 4.
3. L'algorithme supprime tous les éléments du milieu (4) à la limite la plus basse car 59 est supérieur à 24, et le tableau ne contient plus que 5 éléments.
4. Désormais, 59 est supérieur à 45 et inférieur à 63. La valeur du milieu est 7. Par conséquent, la valeur de l'indice de droite devient moyenne – 1, ce qui est égal à 6, et la valeur de l'indice de gauche reste la même qu'auparavant, qui est 5.
5. À ce stade, vous savez que 59 vient après 45. Par conséquent, l’index de gauche, qui est 5, devient également médian.
6. Ces itérations se poursuivent jusqu'à ce que le tableau soit réduit à un seul élément ou que l'élément à trouver devienne le milieu du tableau.

Exemple 2

Regardons l'exemple suivant pour comprendre le fonctionnement de la recherche binaire

1. Vous disposez d’un tableau de valeurs triées allant de 2 à 20 et devez en localiser 18.
2. La moyenne des limites inférieure et supérieure est (l + r) / 2 = 4. La valeur recherchée est supérieure au milieu qui est 4.
3. Les valeurs du tableau inférieures à la valeur moyenne sont supprimées de la recherche et les valeurs supérieures à la valeur moyenne 4 sont recherchées.
4. Il s'agit d'un processus de division récurrent jusqu'à ce que l'élément à rechercher soit trouvé.

Pourquoi avons-nous besoin d’une recherche binaire ?

Les raisons suivantes font de la recherche binaire un meilleur choix comme algorithme de recherche :

• La recherche binaire fonctionne efficacement sur les données triées, quelle que soit leur taille
• Au lieu d'effectuer la recherche en parcourant les données dans une séquence, l'algorithme binaire accède de manière aléatoire aux données pour trouver l'élément requis. Cela rend les cycles de recherche plus courts et plus précis.
• La recherche binaire effectue des comparaisons des données triées sur la base d'un principe d'ordre plutôt que d'utiliser des comparaisons d'égalité, qui sont plus lentes et pour la plupart inexactes.
• Après chaque cycle de recherche, l'algorithme divise la taille du tableau en deux. Ainsi, lors de la prochaine itération, il ne fonctionnera que dans la moitié restante du tableau.

Découvrez notre prochain tutoriel de Recherche linéaire : Python, C++ Exemple

Résumé

• La recherche est un utilitaire qui permet à son utilisateur de rechercher des documents, des fichiers et d'autres types de données. Une recherche binaire est un type avancé d'algorithme de recherche qui recherche et récupère des données à partir d'une liste triée d'éléments.
• La recherche binaire est communément appelée recherche à demi-intervalle ou recherche logarithmique.
• Cela fonctionne en divisant le tableau en deux à chaque itération sous l'élément requis.
• Vue d'ensemble algorithme binaire prend le milieu du tableau en divisant la somme des valeurs d'index les plus à gauche et à droite par 2. Désormais, l'algorithme supprime la limite inférieure ou supérieure des éléments du milieu du tableau, en fonction de l'élément à trouver.
• L'algorithme accède de manière aléatoire aux données pour trouver l'élément requis. Cela rend les cycles de recherche plus courts et plus précis.
• La recherche binaire effectue des comparaisons des données triées sur la base d'un principe de classement plutôt que d'utiliser des comparaisons d'égalité qui sont lentes et inexactes.
• Une recherche binaire ne convient pas aux données non triées.