Algorithmes de recherche binaire itératifs vs récursifs en Python

Dans cet article, vous découvrirez un algorithme de base, que tout informaticien doit connaître :l'algorithme de recherche binaire . J'ai tiré le code de mon livre d'introduction à la programmation NoStarch Python One-Liners :

Recherche binaire d'applications

L'algorithme a d'importantes applications pratiques dans de nombreuses structures de données de base telles que

ensembles,
arbres,
dictionnaires,
sacs, arbres à sacs, dictionnaires de sacs,
jeux de hachage, tables de hachage,
cartes, et
tableaux.

Vous utilisez ces structures de données dans chaque programme non trivial, et dans de nombreux programmes triviaux également ! Ainsi, l'impact d'une recherche efficace est significatif.

Pourquoi le tri naïf est mauvais

Supposons que vous souhaitiez rechercher une liste déjà triée pour la valeur 56.

L'algorithme naïf commence par le premier élément de la liste, vérifie s'il est égal à la valeur 56 et passe à l'élément suivant de la liste - et répète la même procédure jusqu'à ce que l'algorithme ait visité tous les éléments.

Dans le pire des cas (la valeur recherchée n'est pas dans la liste), l'algorithme naïf parcourt tous les éléments de la liste.

Par exemple, la recherche d'une liste triée avec 10 000 éléments nécessiterait environ 10 000 opérations pour vérifier l'égalité de chaque élément de la liste avec la valeur recherchée.

En langage de théorie algorithmique, on dit que la complexité d'exécution est linéaire en nombre d'éléments de liste. Ce n'est en aucun cas optimal, car l'algorithme ne tire pas parti de toutes les informations disponibles pour atteindre la plus grande efficacité.

Après tout, la liste est déjà triée !

Recherche binaire d'idée d'algorithme

En utilisant le fait qu'une liste peut déjà être partiellement triée, nous pouvons créer un algorithme qui ne "touche" que quelques éléments de la liste et sait toujours avec une certitude absolue si un élément existe dans la liste - ou non.

💡 Idée :Au lieu de parcourir tous les éléments d'une liste triée donnée, l'algorithme de recherche binaire ne parcourt que log2(n) éléments (logarithme de base 2). En d'autres termes, nous pouvons rechercher la même liste de 10 000 éléments en utilisant uniquement log2(10,000) <14 au lieu de 10 000 opérations !

Comment rechercher une liste en runtime logarithmique? L'algorithme le plus populaire qui résout ce problème est l'algorithme de recherche binaire .

Ensuite, nous allons trier binairement la liste de manière ascendante.

L'algorithme commence par vérifier l'élément du milieu en premier.
Si notre valeur recherchée est inférieure à cet élément du milieu, nous savons que tous les éléments entre le milieu et le dernier élément de la liste sont supérieurs à la valeur recherchée (à cause de la propriété triée).
L'élément recherché n'existera pas dans cette moitié de la liste, nous pouvons donc immédiatement rejeter la moitié des éléments de la liste en une seule opération.
De même, si la valeur recherchée est supérieure à l'élément du milieu, nous pouvons rejeter la première moitié des éléments de la liste.
Maintenant, nous répétons simplement cette procédure - en divisant par deux la taille effective de la liste des éléments à vérifier à chaque étape de l'algorithme.

Voici un exemple visuel :

La figure montre l'algorithme de recherche binaire au travail. Supposons que vous souhaitiez trouver la valeur 56 dans la liste triée de huit valeurs entières. Récapitulez que notre objectif est de parcourir la liste triée en temps logarithmique, nous ne pouvons donc pas nous permettre de toucher chaque élément de la liste.

L'algorithme de recherche binaire dans le graphique sonde à plusieurs reprises l'élément x au milieu de la liste (arrondi à l'inférieur).

Il y a trois cas :

Élément x est plus grand que la valeur recherchée 56 . Dans ce cas, l'algorithme ignore la partie droite de la liste car tous les éléments sont supérieurs à 56 également car la liste est déjà triée.
Élément x est plus petit que la valeur recherchée 56 . C'est le quoi nous observons sur la figure. Ici, l'algorithme ignore la partie gauche de la liste car elle est également plus petite (encore une fois, en utilisant la propriété que la liste est déjà triée).
Élément x est égal à la valeur recherchée 56 . Vous pouvez voir ce cas dans la dernière ligne de la figure. Félicitations, vous venez de trouver l'élément recherché dans la liste !

A chaque phase de l'algorithme, l'espace de recherche est réduit de moitié. Cela signifie qu'après un nombre logarithmique d'étapes, nous avons trouvé l'élément !

Recherche binaire d'implémentation Python

Voici une implémentation Python pratique de l'algorithme de recherche binaire :

def binary_search(lst, value):
    lo, hi = 0, len(lst)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if lst[mid] < value:
            lo = mid + 1
        elif value < lst[mid]:
            hi = mid - 1
        else:
            return mid
    return -1

    
l = [3, 6, 14, 16, 33, 55, 56, 89]
x = 56
print(binary_search(l,x))
# 6 (the index of the found element)

Liste :L'algorithme de recherche binaire itérative.

L'algorithme prend comme arguments une liste et une valeur à rechercher.

Ensuite, il divise de manière répétée par deux l'espace de recherche en utilisant les deux variables lo et hi .

Ces variables définissent l'intervalle des éléments de liste possibles où la valeur recherchée pourrait exister. L'ancienne variable lo définit l'indice de départ et cette dernière variable hi définit l'indice de fin de l'intervalle.

Nous vérifions à plusieurs reprises dans quel cas parmi les cas ci-dessus le mid l'élément tombe et adaptez l'intervalle des éléments potentiels en conséquence en modifiant le lo et hi valeurs telles que décrites ci-dessus.

Bien que cet algorithme soit une implémentation parfaitement valide, lisible et efficace de l'algorithme de recherche binaire, ce n'est pas encore une solution en une seule ligne !

L'algorithme de recherche binaire récursif

Formulation du problème :Implémentez l'algorithme de recherche binaire en une seule ligne de code !

## The Data
l = [3, 6, 14, 16, 33, 55, 56, 89]
x = 33

## The One-Liner
bs = lambda l, x, lo=0, hi=len(l)-1: -1 if lo>hi else \
         (lo+hi)//2 if l[(lo+hi)//2] == x \
         else bs(l, x, lo, (lo+hi)//2-1) if l[(lo+hi)//2] > x \
         else bs(l, x, (lo+hi)//2+1, hi)


## The Results
print(bs(l, x))

Liste :Solution à une ligne utilisant l'arithmétique de tableau de base.

Exercice :Devinez le résultat de cet extrait de code !

Explication de la recherche binaire à une ligne

Pour plus de lisibilité, j'ai divisé cette solution "one-liner" en quatre lignes - même si vous pouviez l'écrire en une seule ligne de code. Il est souvent préférable de limiter la longueur d'une seule ligne car cela facilite la compréhension du code par les lecteurs.

J'ai utilisé une méthode récursive pour définir l'algorithme de recherche binaire en quatre étapes :

Étape 1

Nous créons une nouvelle fonction bs en utilisant l'opérateur lambda avec quatre arguments :l , x , lo , et hi .

Les deux premiers arguments l et x définir la liste triée et la valeur à rechercher.
Les deux derniers arguments hi et lo définir l'index minimal et maximal de la sous-liste courante à rechercher pour la valeur x .

A chaque niveau de récursivité, on considère une sous-liste (comme spécifié par les indices hi et lo ) qui devient de plus en plus petit en augmentant l'indice lo et en diminuant l'indice hi .

Après un nombre fini d'étapes, la condition lo>hi contient True . C'est le cas de base de notre récursivité et si nous n'avons pas trouvé l'élément recherché x maintenant, nous renvoyons -1 indiquant qu'aucun élément de ce type n'existe.

Étape 2

On renvoie l'indice (lo+hi)//2 du mid élément (dans la sous-liste spécifiée) si cet élément est la valeur recherchée.

Notez que nous utilisons la division entière pour arrondir à la valeur entière suivante qui peut être utilisée comme liste indice.

Étape 3

Cependant, si le mid l'élément est plus grand que la valeur recherchée, il n'est pas nécessaire de rechercher tous les éléments à droite du mid élément. Ces éléments seront également plus grands car la liste est triée.

Par conséquent, nous appelons la fonction de manière récursive mais adaptons le hi index pour ne considérer que les éléments de la liste à gauche du mid élément.

Étape 4

De même, si le mid l'élément est plus petit que la valeur recherchée, il n'est pas nécessaire de rechercher tous les éléments à gauche du mid élément. Par conséquent, nous appelons la fonction de manière récursive mais adaptons le lo index pour ne considérer que les éléments de la liste à droite du mid élément.

Ainsi, lors de la recherche de la valeur 33 dans la liste [3, 6, 14, 16, 33, 55, 56, 89] , le résultat est l'indice 4.

J'espère que cet article a amélioré vos compétences générales de compréhension du code concernant diverses fonctionnalités Python telles que l'exécution conditionnelle, les mots-clés de base, les opérations arithmétiques et le sujet important de l'indexation de séquences programmatiques. Mais plus important encore, vous avez appris à utiliser la récursivité pour simplifier les problèmes complexes.