Travailler avec des listes triées peut parfois être un peu délicat. Vous devez conserver l'ordre de la liste après chaque insertion et rechercher efficacement les éléments qu'elle contient. La recherche binaire est un algorithme puissant pour rechercher dans une liste triée. Même si sa mise en œuvre à partir de zéro n’est pas trop difficile, cela peut prendre du temps. Heureusement, Python propose le module bisect, qui facilite grandement la gestion des listes triées.

Qu’est-ce que la recherche binaire ?

La recherche binaire est un algorithme qui trouve la position d'une valeur cible dans un tableau trié. Imaginez que vous recherchez un nom dans un annuaire téléphonique. Au lieu de commencer par la première page, vous commencerez probablement au milieu du livre et déciderez de poursuivre la recherche dans la première ou la seconde moitié, selon que le nom est alphabétiquement supérieur ou inférieur à celui du milieu. La recherche binaire fonctionne de manière similaire : elle commence par deux pointeurs, l'un au début et l'autre à la fin de la liste. L'élément du milieu est ensuite calculé et comparé à la cible.

Le module bisect : simplifier les opérations de liste triée

Bien que la recherche binaire soit efficace, écrire l'implémentation à chaque fois peut être fastidieux. Et si vous pouviez effectuer les mêmes opérations avec une seule ligne de code ? C'est là qu'intervient le module bisect de Python. Faisant partie de la bibliothèque standard de Python, bisect vous aide à maintenir une liste triée sans avoir besoin de la trier après chaque insertion. Il le fait en utilisant un simple algorithme de bissection.

Le module bisect fournit deux fonctions clés : bisect et insort. La fonction bisect trouve l'index où un élément doit être inséré pour garder la liste triée, tandis que insort insère l'élément dans la liste tout en conservant son ordre de tri.

Utilisation du module bisect : un exemple pratique

Commençons par importer le module :

import bisect

Exemple 1 : insertion d'un numéro dans une liste triée

Supposons que nous ayons une liste triée de nombres :

data = [1, 3, 5, 6, 8]

Pour insérer un nouveau numéro tout en gardant la liste triée, utilisez simplement :

bisect.insort(data, 7)

après avoir exécuté ce code, les données ressembleront à ceci :

[1, 3, 5, 6, 7, 8]

Exemple 2 : Trouver le point d'insertion

Que se passe-t-il si vous souhaitez simplement savoir où un nombre serait inséré sans réellement l'insérer ? Vous pouvez utiliser les fonctions bisect_left ou bisect_right :

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

Cela nous indique que le chiffre 4 doit être inséré à l'index 2 pour garder la liste triée.

Exemple 3 : Maintenir l'ordre de tri dans une liste dynamique

Disons que vous gérez une liste à croissance dynamique et que vous devez insérer des éléments tout en vous assurant qu'elle reste triée :

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

Cela affichera la liste à chaque étape au fur et à mesure que les éléments sont insérés :

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

Exemple 4 : Utilisation de la bisecte avec des objets personnalisés

Supposons que vous disposiez d'une liste d'objets personnalisés, tels que des tuples, et que vous souhaitiez les insérer en fonction d'un critère spécifique :

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

Ou vous souhaiterez peut-être insérer en fonction du deuxième élément de chaque tuple :

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

bisect en action : à la recherche de mots

Le module bisect ne se limite pas aux nombres ; cela peut également être utile pour rechercher dans des listes de chaînes, de tuples, de caractères, etc.
Par exemple, pour rechercher un mot dans une liste triée :

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

Ou pour rechercher le premier mot d'un groupe de mots avec un préfixe spécifique :

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix   'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

Cependant, gardez à l'esprit que bisect_left renvoie l'index où la cible doit être insérée, et non si la cible existe dans la liste.

Variantes de bissect et insort

Le module comprend également des variantes du côté droit : bisect_right et insort_right. Ces fonctions renvoient l'index le plus à droite auquel insérer un élément s'il est déjà dans la liste. Par exemple, bisect_right renverra l'index du premier élément supérieur à la cible si la cible est dans la liste, tandis que insort_right insère l'élément à cette position.

diviser sous le capot

La puissance du module bisect réside dans sa mise en œuvre efficace de l'algorithme de recherche binaire. Lorsque vous appelez bisect.bisect_left, par exemple, la fonction effectue essentiellement une recherche binaire sur la liste pour déterminer le point d'insertion correct pour le nouvel élément.

Voici comment cela fonctionne sous le capot :

1. Initialisation : la fonction commence par deux pointeurs, lo et hi, qui représentent les limites inférieure et supérieure de la plage de recherche dans la liste. Initialement, lo est défini au début de la liste (index 0) et hi est défini à la fin de la liste (index égal à la longueur de la liste). Mais vous pouvez également spécifier des valeurs lo et hi personnalisées pour effectuer une recherche dans une plage spécifique de la liste.

2. Bisection : dans une boucle, la fonction calcule le point médian (milieu) entre lo et hi. Il compare ensuite la valeur médiane avec la valeur cible que vous souhaitez insérer.

3. Comparaison:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid   1`.

1. Terminaison : ce processus se poursuit, réduisant de moitié la plage de recherche à chaque fois, jusqu'à ce que lo soit égal à hi. À ce stade, lo (ou hi) représente l'index correct où la cible doit être insérée pour conserver l'ordre de tri de la liste.

2. Insertion : Pour la fonction d'insertion, une fois l'index correct trouvé à l'aide de bisect_left, la cible est insérée dans la liste à cette position.

Cette approche garantit que le processus d'insertion est efficace, avec une complexité temporelle de O(log n) pour la recherche et de O(n) pour l'insertion en raison de l'opération de décalage de liste. C'est nettement plus efficace que de trier la liste après chaque insertion, en particulier pour les grands ensembles de données.

exemple de code bisect_left :

    if lo 



exemple de code insort_left :


def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)





  
  
  Conclusion


Le module bisect rend le travail avec des listes triées simple et efficace. La prochaine fois que vous devrez effectuer une recherche binaire ou insérer des éléments dans une liste triée, n'oubliez pas le module bisect et économisez du temps et des efforts.