Algorithme de recherche binaire avec EXEMPLE

Avant d'apprendre la recherche binaire, voyons ce qu'est la recherche.

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 ?

La recherche binaire est un type avancé d'algorithme de recherche qui permet de trouver et d'extraire des données d'une liste triée d'éléments. Son principe de fonctionnement consiste à diviser les données de la liste en deux jusqu'à trouver la valeur recherchée et l'afficher à l'utilisateur dans les résultats. La recherche binaire est communément appelée recherche par paires. recherche à demi-intervalle recherche logarithmique.

Comment fonctionne la recherche binaire ?

La recherche binaire fonctionne de la manière suivante :

• Le processus de recherche commence par la localisation de l'élément central du tableau de données trié.
• Ensuite, la valeur clé est comparée à l'élément.
• Si la valeur clé est inférieure à l'élément central, la recherche analyse les valeurs supérieures à l'élément central à des fins de comparaison et de correspondance.
• Si la valeur clé est supérieure à l'élément central, la recherche analyse les valeurs inférieures à l'élément central à des fins de comparaison et de correspondance.

Algorithme de recherche binaire (pseudocode)

La recherche binaire peut être décrite comme une courte routine itérative. Elle utilise deux pointeurs, l'un vers le bas et l'autre vers le haut, et réduit l'intervalle de recherche jusqu'à ce que la cible soit trouvée ou que l'intervalle soit vide.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

La routine renvoie l'indice de la cible en cas de succès et -1 si la valeur est absente. Comme la plage est divisée par deux à chaque itération, la boucle s'exécute au maximum log₂(n) fois.

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. Chaque élément est indexé de 0 à 9. On calcule ensuite la valeur centrale du tableau. Pour cela, on divise les valeurs extrêmes de l'indice par 2. Le résultat est 4.5, mais on arrondit à l'entier inférieur. La valeur centrale est donc 4.
3. L'algorithme supprime tous les éléments du milieu (4) jusqu'à la limite inférieure, car 59 est supérieur à 24, et il ne reste plus que 5 éléments dans le tableau.
4. Or, 59 est supérieur à 45 et inférieur à 63. La valeur médiane est 7. Par conséquent, la valeur de l'indice de droite devient médiane − 1, ce qui est égal à 6, et la valeur de l'indice de gauche reste la même qu'auparavant, soit 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

Prenons 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 à la médiane, qui est 4.
3. Les valeurs du tableau inférieures à la valeur médiane sont supprimées de la recherche, et les valeurs supérieures à la valeur médiane 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 en tant qu'algorithme de recherche :

• La recherche binaire fonctionne efficacement sur des 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 de données triées en fonction d'un principe d'ordre plutôt qu'en utilisant des comparaisons d'égalité, qui sont plus lentes et généralement imprécises.
• Après chaque cycle de recherche, l'algorithme divise la taille du tableau en deux ; par conséquent, à l'itération suivante, il ne travaillera que sur la moitié restante du tableau.

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

Recherche binaire vs recherche linéaire

La recherche binaire et la recherche linéaire sont les deux méthodes les plus courantes pour trouver une valeur dans une collection. Le tableau ci-dessous met en évidence leurs différences :

En résumé, la recherche binaire est beaucoup plus rapide sur de grands volumes de données triées, tandis que la recherche linéaire est plus simple et la seule option lorsque les données ne sont pas triées.

FAQ