bisect_left în loc de bisect_right: numărul de valori dintr-un interval iese prea mic
bisect_left(lista, b) dă poziția dinaintea primei apariții a lui b, deci valorile egale cu b nu sunt numărate. Pentru câte valori sunt în intervalul [a, b] folosește bisect_right(lista, b) - bisect_left(lista, a).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Pe o listă sortată, bisect_left(lista, x) returnează primul index la care ai putea insera x înaintea tuturor valorilor egale cu el, iar bisect_right(lista, x) (sau bisect.bisect) returnează indexul de după ultima valoare egală. Diferența dintre ele e exact numărul de apariții ale lui x.
Pentru a număra valorile din intervalul închis [a, b], capătul din stânga trebuie să includă valorile egale cu a (deci bisect_left), iar capătul din dreapta să includă valorile egale cu b (deci bisect_right). Dacă folosești bisect_left la ambele capete, numeri de fapt [a, b) și pierzi toate valorile egale cu b.
Nu primești nicio eroare. Greșeala se vede doar când în listă există valori egale cu capetele, adică exact cazurile pe care le verifică testele.
De ce apare: cauzele frecvente
1bisect_left la capătul din dreapta
return bisect_left(note, b) - bisect_left(note, a)return bisect_right(note, b) - bisect_left(note, a)bisect_right(note, b) trece de toate notele egale cu b, deci ele intră în numărătoare.
2Numărul de apariții ale unei valori
aparitii = bisect_right(nums, x) - bisect_right(nums, x - 1) - 1aparitii = bisect_right(nums, x) - bisect_left(nums, x)Formula cu x - 1 merge doar pentru numere întregi și oricum are un -1 în plus. Diferența dintre dreapta și stânga pentru aceeași valoare e directă.
3Verifici existența cu bisect_right
i = bisect_right(nums, x)
exista = i < len(nums) and nums[i] == xi = bisect_left(nums, x)
exista = i < len(nums) and nums[i] == xbisect_right sare peste valorile egale, deci nums[i] e deja mai mare decât x. bisect_left indică prima apariție.
Repară eroarea, direct în pagină
Funcția cate_note(note, a, b) numără câte note dintr-un catalog sortat sunt între a și b, inclusiv capetele. Testul cu assert pică: notele egale cu b nu sunt numărate. Repar-o ca să afișeze 5, 3 și 0.
from bisect import bisect_left, bisect_right
def cate_note(note, a, b):
return bisect_left(note, b) - bisect_left(note, a)
note = [4, 5, 5, 7, 7, 7, 9, 10]
for a, b, corect in [(5, 7, 5), (7, 7, 3), (1, 3, 0)]:
rez = cate_note(note, a, b)
assert rez == corect, f'interval gresit: {rez} in loc de {corect}'
print(rez)5 3 0
Indiciu
La capătul din dreapta ai nevoie de poziția de după ultima notă egală cu b.
Reparația
from bisect import bisect_left, bisect_right
def cate_note(note, a, b):
return bisect_right(note, b) - bisect_left(note, a)
note = [4, 5, 5, 7, 7, 7, 9, 10]
for a, b, corect in [(5, 7, 5), (7, 7, 3), (1, 3, 0)]:
rez = cate_note(note, a, b)
assert rez == corect, f'interval gresit: {rez} in loc de {corect}'
print(rez)De ce merge
bisect_left(note, 7) dă 3, poziția primului 7, deci cei trei de 7 rămâneau în afara numărătorii. bisect_right(note, 7) dă 6, poziția de după ultimul 7. Diferența 6 - bisect_left(note, 5) = 6 - 1 = 5 numără cele două note de 5 și cele trei de 7. Pentru intervalul [1, 3], ambele poziții sunt 0, deci rezultatul e 0.
Cum o eviți pe viitor
Când folosești bisect, scrie-ți regula lângă cod: left = primul index cu valoare >= x, right = primul index cu valoare > x. Pentru intervale închise, stânga cu left, dreapta cu right. Testează mereu pe o listă cu valori repetate chiar la capetele intervalului și pe un interval care nu conține nimic.
Întrebări frecvente
bisect.bisect e același lucru cu bisect_right?
Da, bisect.bisect e un alias pentru bisect_right.
Merge pe o listă nesortată?
Nu. Toate funcțiile din bisect presupun o listă sortată crescător; pe una nesortată rezultatele sunt fără sens.
Erori înrudite
bisect dă poziții greșite pe o listă nesortată bisect (și orice căutare binară) presupune că lista e sortată crescător. Pe o listă nesortată nu dă eroare, dar returnează poziții fără sens. Sortează lista o dată înainte (lista.sort()) sau păstreaz-o sortată cu bisect.insort. Căutarea binară returnează o apariție oarecare, nu prima, când valoarea se repetă Căutarea binară clasică se oprește la prima potrivire întâlnită, care poate fi oricare dintre valorile egale. Ca să găsești prima apariție, când nums[mijloc] == x salvează poziția și continuă căutarea în stânga (dreapta = mijloc - 1). Căutarea binară nu găsește elementul de la capăt (while stanga < dreapta) Ai folosit while stanga < dreapta cu intervalul închis [0, len - 1] și actualizări mijloc + 1 / mijloc - 1. Bucla se oprește când rămâne un singur element, fără să-l verifice, deci returnează -1 deși valoarea există. Folosește while stanga <= dreapta. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
