bisect_left et bisect_right
Trouver les positions d’insertion dans une liste triée
bisect_left et bisect_right est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Recherchez sans code répétitif
Le module bisect de Python fournit une recherche binaire fiable pour les listes triées. Une boucle écrite à la main signifie qu’il n’y a aucun bogue de décalage d’indice à déboguer.
import bisectDes points d’insertion, pas des booléens
Au lieu de renvoyer vrai ou faux, bisect renvoie un indice où une valeur serait insérée pour conserver la liste triée. Cet indice constitue sa véritable puissance.
a = [1, 3, 3, 3, 7]bisect_left privilégie la gauche
bisect_left renvoie la première position où la valeur pourrait être placée. En présence de doublons, il se place avant tous les éléments égaux, jamais après.
bisect.bisect_left(a, 3) # 1bisect_right privilégie la droite
bisect_right renvoie la position juste après le dernier élément égal. En présence de doublons, il se place après toutes les valeurs correspondantes.
bisect.bisect_right(a, 3) # 4Comptez les éléments égaux
Soustrayez les deux pour compter les doublons d’une valeur en O(log n). right moins left donne exactement le nombre d’occurrences.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3La valeur existait-elle
Pour vérifier l’appartenance, obtenez i avec bisect_left et vérifiez que a[i] est égal à la cible. Vérifiez d’abord que i n’a pas atteint la longueur de la liste.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xPremier élément au moins égal à X
bisect_left trouve aussi le premier élément supérieur ou égal à x. Cet indice pointe directement vers votre réponse de borne inférieure.
i = bisect.bisect_left(a, x) # first >= xPremier élément strictement supérieur
Vous avez besoin du premier élément strictement supérieur à x ? bisect_right fournit directement cet indice, l’équivalent de la borne supérieure.
i = bisect.bisect_right(a, x) # first > xInsérez tout en conservant le tri
insort trouve l’emplacement et insère l’élément en un seul appel, tout en conservant la liste ordonnée. C’est pratique lorsque vous construisez une structure triée au fil de l’eau.
bisect.insort(a, 5) # a stays sortedRecherchez dans une fenêtre
Les arguments facultatifs lo et hi limitent la recherche à une sous-liste. Cela évite une copie lorsque seule une sous-plage vous intéresse.
bisect.bisect_left(a, x, 2, 5)Des clés via une liste auxiliaire
bisect compare les éléments entiers, donc, pour rechercher selon un champ, construisez une liste parallèle contenant uniquement ces clés et appliquez plutôt bisect à celle-ci.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)Vérification rapide
Raisonnez sur les doublons et les points d’insertion.
Récapitulatif : maîtriser bisect
Vous savez maintenant trouver des points d’insertion, compter les doublons et localiser les bornes inférieure et supérieure en temps logarithmique. Utilisez bisect avant d’écrire une boucle. ✨
Questions Fréquemment Posées
La leçon « bisect_left et bisect_right » est-elle gratuite ?
Oui — le texte complet de « bisect_left et bisect_right » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « bisect_left et bisect_right » ?
Trouver les positions d’insertion dans une liste triée Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « bisect_left et bisect_right » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Recherche binaire classique sans erreurs
- bisect_left et bisect_right
- Premier True : recherche binaire par prédicat
- Recherche binaire sur la réponse