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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
bisect_left și bisect_right din modulul bisect fac o căutare binară: compară cu elementul din mijloc și aruncă jumătatea în care valoarea „sigur nu e”. Raționamentul e corect doar dacă lista e sortată crescător. Pe o listă nesortată, funcțiile nu verifică nimic și nu dau eroare: returnează o poziție, dar ea nu înseamnă nimic.
Simptomele tipice: numărul de elemente mai mici decât un prag e greșit, insort pune elementul în locul greșit, iar o căutare „nu găsește” o valoare care e în listă. Aceeași problemă apare la căutarea binară scrisă de mână.
În „Repară tu” testul cu assert afișează rezultatul real. Reparația e să sortezi o singură dată la început (O(n log n)), apoi fiecare căutare e O(log n).
De ce apare: cauzele frecvente
1Lista de prețuri nu e sortată
from bisect import bisect_right
preturi = [30, 10, 50, 20]
print(bisect_right(preturi, 35))from bisect import bisect_right
preturi = sorted([30, 10, 50, 20])
print(bisect_right(preturi, 35))Pe lista sortată [10, 20, 30, 50] rezultatul 3 înseamnă „trei prețuri ≤ 35”. Pe cea nesortată poziția nu are sens.
2Lista e sortată descrescător
note = [10, 9, 7, 5]
poz = bisect_left(note, 8)note = [10, 9, 7, 5]
poz = bisect_left(note, -8, key=lambda x: -x)bisect presupune ordine crescătoare. Pentru o listă descrescătoare, compară pe valori negate (parametrul key există din Python 3.10).
3Lista a fost modificată cu append după sortare
stoc.sort()
stoc.append(3)
bisect_left(stoc, 3)stoc.sort()
bisect.insort(stoc, 3)
bisect_left(stoc, 3)append pune elementul la coadă și strică ordinea. insort îl inserează pe poziția corectă.
Repară eroarea, direct în pagină
Funcția cate_incap(preturi, buget) numără câte produse costă cel mult buget, folosind bisect_right. Testul cu assert pică. Repar-o ca testele să treacă și să afișeze 3, 4 și 0.
from bisect import bisect_right
def cate_incap(preturi, buget):
return bisect_right(preturi, buget)
preturi = [30, 10, 50, 20, 40]
for buget, corect in [(35, 3), (45, 4), (5, 0)]:
rez = cate_incap(preturi, buget)
assert rez == corect, f'numar gresit pentru {buget}: {rez}'
print(rez)3 4 0
Indiciu
Căutarea binară are nevoie de o listă sortată crescător.
Reparația
from bisect import bisect_right
def cate_incap(preturi, buget):
return bisect_right(sorted(preturi), buget)
preturi = [30, 10, 50, 20, 40]
for buget, corect in [(35, 3), (45, 4), (5, 0)]:
rez = cate_incap(preturi, buget)
assert rez == corect, f'numar gresit pentru {buget}: {rez}'
print(rez)De ce merge
Pe lista nesortată, bisect_right compara cu 50 din mijloc, decidea că tot ce urmează e mai mare și ignora 20 și 40. Pe lista sortată [10, 20, 30, 40, 50] raționamentul e corect: poziția returnată e exact numărul de prețuri ≤ buget. Dacă ai multe întrebări pe aceeași listă, sortează o singură dată în afara funcției, ca fiecare întrebare să coste doar O(log n).
Cum o eviți pe viitor
Înainte de orice căutare binară, întreabă-te: „lista e sortată, și crescător?”. Sortează o singură dată după ce o construiești și folosește insort pentru adăugări. În timpul dezvoltării poți pune un assert lista == sorted(lista) înainte de căutări (scoate-l apoi, e O(n log n)). Pentru căutarea binară pe răspuns, verifică faptul că condiția e monotonă.
Întrebări frecvente
De ce bisect nu verifică dacă lista e sortată?
Verificarea ar costa O(n), iar căutarea binară e utilă tocmai pentru că e O(log n). Responsabilitatea e a ta.
Care e diferența dintre bisect_left și bisect_right?
La valori egale, bisect_left dă poziția dinaintea lor, iar bisect_right pe cea de după. bisect_right(lista, x) e numărul elementelor ≤ x.
Erori înrudite
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. TypeError: 'module' object is not callable. Did you mean: 'bisect.bisect(...)'? Ai importat modulul (import bisect) și apoi l-ai apelat ca pe o funcție: bisect(lista, x). Modulul conține funcțiile, deci scrie bisect.bisect_left(lista, x) sau importă direct funcția: from bisect import bisect_left. Căutarea binară intră în buclă infinită (stanga = mijloc) Când ai actualizat capătul cu stanga = mijloc (sau dreapta = mijloc într-o buclă cu <=), intervalul nu se mai micșorează și bucla se repetă la nesfârșit; editorul oprește programul după limita de timp. Mută capătul dincolo de mijloc: stanga = mijloc + 1 și dreapta = mijloc - 1. Î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.
