8.6. "bisect" — Algorithme de bissection de listes
**************************************************

**Code source :** Lib/bisect.py

======================================================================

Ce module fournit des outils pour maintenir une liste triée sans avoir
à la trier à chaque insertion. Il pourrait être plus rapide que
l'approche classique pour de longues listes d'éléments dont les
opérations de comparaison sont lourdes. Le module se nomme "bisect"
car il utilise une approche simple par bissection. Si vous voulez un
exemple de cet algorithme, le mieux est d'aller lire le code source de
ce module (les conditions sur les limites y étant justes !).

Les fonctions suivantes sont fournies :

bisect.bisect_left(a, x, lo=0, hi=len(a))

   Trouve le point d'insertion de *x* dans *a* permettant de conserver
   l'ordre. Les paramètres *lo* et *hi* permettent de limiter les
   emplacements à vérifier dans la liste, par défaut toute la liste
   est utilisée. Si *x* est déjà présent dans *a*, le point
   d'insertion proposé sera avant (à gauche) de l'entrée existante. Si
   *a* est déjà triée, la valeur renvoyée peut directement être
   utilisée comme premier paramètre de "list.insert()".

   Le point d'insertion renvoyé, *i*, coupe la liste *a* en deux
   moitiés telles que, pour la moitié de gauche : "all(val < x for val
   in a[lo:i])", et pour la partie de droite : "all(val >= x for val
   in a[i:hi])".

bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))

   Semblable à "bisect_left()", mais renvoie un point d'insertion
   après (à droite) d'une potentielle entrée existante valant *x* dans
   *a*.

   Le point d'insertion renvoyé, *i*, coupe la liste *a* en deux
   moitiés telles que, pour la moitié de gauche : "all(val <= x for
   val in a[lo:i])" et pour la moitié de droite : "all(val > x for val
   in a[i:hi])".

bisect.insort_left(a, x, lo=0, hi=len(a))

   Insère *x* dans *a* en conservant le tri.  C'est l'équivalent de
   "a.insert(bisect.bisect_left(a, x, lo, hi), x)", tant que *a* est
   déjà triée. Gardez en tête que bien que la recherche ne coûte que
   O(log n), l'insertion coûte O(n).

bisect.insort_right(a, x, lo=0, hi=len(a))
bisect.insort(a, x, lo=0, hi=len(a))

   Similaire à "insort_left()", mais en insérant *x* dans *a* après
   une potentielle entrée existante égale à *x*.

Voir aussi:

  SortedCollection recipe utilise le module *bisect* pour construire
  une classe collection exposant des méthodes de recherches naturelles
  et gérant une fonction clef.  Les clefs sont pré-calculées pour
  économiser des appels inutiles à la fonction clef durant les
  recherches.


8.6.1. Chercher dans des listes triées
======================================

Les fonctions "bisect()" ci-dessus sont utiles pour insérer des
éléments, mais peuvent être étranges et peu naturelles à utiliser pour
rechercher des éléments. Les cinq fonctions suivantes montrent comment
les transformer en recherche plus classique pour les listes triées :

   def index(a, x):
       'Locate the leftmost value exactly equal to x'
       i = bisect_left(a, x)
       if i != len(a) and a[i] == x:
           return i
       raise ValueError

   def find_lt(a, x):
       'Find rightmost value less than x'
       i = bisect_left(a, x)
       if i:
           return a[i-1]
       raise ValueError

   def find_le(a, x):
       'Find rightmost value less than or equal to x'
       i = bisect_right(a, x)
       if i:
           return a[i-1]
       raise ValueError

   def find_gt(a, x):
       'Find leftmost value greater than x'
       i = bisect_right(a, x)
       if i != len(a):
           return a[i]
       raise ValueError

   def find_ge(a, x):
       'Find leftmost item greater than or equal to x'
       i = bisect_left(a, x)
       if i != len(a):
           return a[i]
       raise ValueError


8.6.2. Autres Exemples
======================

La fonction "bisect()" peut être utile pour des recherches dans des
tableaux de nombres. Cet exemple utilise "bisect()" pour rechercher la
note (sous forme de lettre) correspondant à un note sous forme de
points, en se basant sur une échelle prédéfinie : plus de 90 vaut 'A',
de 80 à 89 vaut 'B', etc… :

   >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
   ...     i = bisect(breakpoints, score)
   ...     return grades[i]
   ...
   >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
   ['F', 'A', 'C', 'C', 'B', 'A', 'A']

Contrairement à la fonction "sorted()", ça n'aurait pas de sens pour
la fonction "bisect()" d'avoir un paramètre *key* ou *reversed*, qui
conduiraient à une utilisation inefficace (des appels successifs à la
fonction *bisect* n'auraient aucun moyen de se "souvenir" des
recherches de clef précédentes).

Il est préférable d'utiliser une liste de clefs pré-calculée pour
chercher l'index de l'enregistrement en question :

   >>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
   >>> data.sort(key=lambda r: r[1])
   >>> keys = [r[1] for r in data]         # precomputed list of keys
   >>> data[bisect_left(keys, 0)]
   ('black', 0)
   >>> data[bisect_left(keys, 1)]
   ('blue', 1)
   >>> data[bisect_left(keys, 5)]
   ('red', 5)
   >>> data[bisect_left(keys, 8)]
   ('yellow', 8)
