L'algorithme de recherche binaire en Python

Défi :Comment retrouver une valeur donnée dans une liste triée ?

Exemple :Supposons que vous ayez une liste triée :

[1, 4, 10, 42, 99, 102, 103, 999]

Votre but est de trouver l'index de l'élément 103 dans la liste. Faut-il vérifier tous les éléments pour cela ?

Eh bien, seulement si vous avez utilisé le …

Algorithme de recherche de liste naïve

Un algorithme naïf va comparer chaque élément dans la liste par rapport à la valeur recherchée.

Par exemple, considérons une liste de 1024 éléments. L'algorithme naïf fonctionne dans l'ordre de 1024 comparaisons dans le pire des cas . ?

(Au cas où vous vous poseriez la question, c'est vraiment mauvais - vérifier n'importe quel élément dans une liste triée pour trouver un élément spécifique est une chose stupide à faire !)

En informatique, la complexité d'exécution dans le pire des cas peut être exprimée via la notation Big-O. On dit, pour n éléments dans une liste, l'algorithme naïf a besoin de O(n) comparaisons. La fonction O définit la croissance asymptotique dans le pire des cas.

Heureusement, il existe un moyen meilleur et plus rapide de trouver un élément dans une liste triée !

Algorithme de recherche binaire en Python

La fonction bsearch est un moyen plus efficace de trouver une valeur dans une liste triée. Pour n éléments de la liste, il n'a besoin d'effectuer que O(log(n)) comparaisons.

Voici le code :

def bsearch(l, value):
    # search only in index interval (lo:hi)
    lo, hi = 0, len(l)-1
    
    while lo <= hi:
        mid = (lo + hi) // 2
        if l[mid] < value:
            # Mid element is smaller
            # --> skip all left elements
            lo = mid + 1
        elif l[mid] > value:
            # Mid element is larger
            # --> skip all right elements
            hi = mid - 1
        else:
            # We've found the value!
            return mid
    return -1

Exercice  :Devinez :quelle est la sortie de cet extrait de code lors du passage des trois appels de fonction suivants ?

l = [0, 1, 2, 3, 4, 5, 6]

x = 6
print(bsearch(l,x))

x = 0
print(bsearch(l,x))

x = 3
print(bsearch(l,x))

Au cas où vous auriez deviné les trois valeurs suivantes, vous avez bien deviné !

6
0
3

Appliqué à une liste de 1024 éléments, bsearch ne nécessite que jusqu'à log(1024)=10 comparaisons. Donc, bsearch est beaucoup plus rapide que l'algorithme de comparaison naïf !

En informatique, la complexité d'exécution dans le pire des cas peut être exprimée via la notation Big-O. On dit, pour n éléments dans une liste, l'algorithme naïf a besoin de O(n) comparaisons. La fonction O définit la croissance asymptotique dans le pire des cas.

Oui, cela fait environ 25 comparaisons pour une liste de 42 000 000 d'éléments !!

? <— Vous

Pourquoi Bsearch est-il si rapide ?

L'algorithme naïf compare tous les éléments avec la valeur recherchée.

Au lieu de cela, bsearch utilise la propriété selon laquelle la liste est triée de manière ascendante.

• Il vérifie uniquement l'élément en position médiane entre deux indices lo et hi .
• Si cet élément du milieu est plus petit que la valeur recherchée, tous les éléments de gauche seront également plus petits en raison de la liste triée. Par conséquent, nous définissons l'indice inférieur lo à la position à droite de l'élément du milieu.
• Si cet élément du milieu est plus grand que la valeur recherchée, tous les éléments de droite seront également plus grands. Par conséquent, nous définissons l'indice supérieur hi à la position à gauche de l'élément du milieu.
• Ce n'est que si l'élément du milieu est exactement le même que la valeur recherchée que nous renvoyons l'index de cette position.

Cette procédure est répétée jusqu'à ce que nous trouvions la valeur recherchée ou qu'il ne reste plus de valeurs. À chaque itération de boucle, nous réduisons l'espace de recherche , c'est-à-dire le nombre d'éléments entre lo et hi , de moitié.

Python de recherche binaire shell interactif

Vous pouvez essayer le bsearch fonction dans le shell interactif suivant de votre navigateur :

Exercice  :Devinez la sortie et exécutez le shell pour la comparer à la sortie réelle !

Algorithme de recherche binaire Code Puzzle

Un autre excellent moyen d'améliorer votre compréhension des concepts de programmation tels que l'algorithme de recherche binaire consiste à résoudre des énigmes de code :

Exercice :Êtes-vous un maître codeur ? Testez vos compétences maintenant! Cliquez sur l'image du puzzle et essayez de le résoudre dans notre application de puzzle interactive !

Recherche binaire de vidéo associée