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 basique fonctionne.
Qu'est-ce que la recherche binaire?
Une recherche binaire est un type avancé d'algorithme de recherche qui trouve et récupère des données à partir d'une liste triée d'éléments. Son principe de fonctionnement de base consiste à diviser les données de la liste par moitié 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 .
Dans ce didacticiel sur l'algorithme, vous apprendrez:
- Qu'est-ce que la recherche?
- Qu'est-ce que la recherche binaire?
- Comment fonctionne la recherche binaire?
- Exemple de recherche binaire
- Pourquoi avons-nous besoin d'une recherche binaire?
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 trié de données
- Après cela, la valeur clé est comparée à l'élément
- Si la valeur de la clé est plus petite que l'élément du milieu, les recherches analysent les valeurs supérieures de l'élément du milieu à des fins de comparaison et de correspondance.
- Si la valeur de la clé est supérieure à l'élément du milieu, la recherche analyse les valeurs inférieures de 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:
- Vous avez un tableau de 10 chiffres et l'élément 59 doit être trouvé.
- Tous les éléments sont marqués avec l'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. Par conséquent, le milieu est 4.
- L'algorithme supprime tous les éléments du milieu (4) à la borne la plus basse car 59 est supérieur à 24, et maintenant le tableau ne contient que 5 éléments.
- Maintenant, 59 est supérieur à 45 et inférieur à 63. Le milieu est 7. Par conséquent, la valeur d'index de droite devient middle - 1, ce qui est égal à 6, et la valeur d'index de gauche reste la même qu'avant, qui est de 5.
- À ce stade, vous savez que 59 vient après 45. Par conséquent, l'index de gauche, qui est 5, devient également milieu.
- 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
- Vous disposez d'un tableau de valeurs triées allant de 2 à 20 et devez localiser 18.
- La moyenne des limites inférieure et supérieure est (l + r) / 2 = 4. La valeur recherchée est supérieure à la moyenne qui est de 4.
- Les valeurs de tableau inférieures au milieu sont supprimées de la recherche et les valeurs supérieures à la valeur moyenne 4 sont recherchées.
- Il s'agit d'un processus de division récurrent jusqu'à ce que l'élément réel à rechercher soit trouvé.
Pourquoi avons-nous besoin d'une recherche binaire?
Les raisons suivantes font de la recherche binaire un meilleur choix à utiliser comme algorithme de recherche:
- La recherche binaire fonctionne efficacement sur les données triées, quelle que soit la taille des données
- 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 en fonction d'un principe de classement plutôt qu'en utilisant des comparaisons d'égalité, qui sont plus lentes et généralement inexactes.
- Après chaque cycle de recherche, l'algorithme divise la taille du tableau en deux, donc lors de la prochaine itération, il ne fonctionnera que dans la moitié restante du tableau
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 trouve 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.
- L'algorithme binaire prend le milieu du tableau en divisant la somme des valeurs d'index les plus à gauche et à droite par 2. À présent, l'algorithme supprime la limite inférieure ou supérieure des éléments à partir 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 en fonction d'un principe de classement plutôt qu'en utilisant des comparaisons d'égalité qui sont lentes et inexactes.
- Une recherche binaire ne convient pas aux données non triées.