...
Eroare Algoritmi și structuri de date · Căutare binară și sortări

bisect dă poziții greșite pe o listă nesortată

Pe scurt

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ă

Greșit
PYTHON
from bisect import bisect_right
preturi = [30, 10, 50, 20]
print(bisect_right(preturi, 35))
Corect
PYTHON
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

Greșit
PYTHON
note = [10, 9, 7, 5]
poz = bisect_left(note, 8)
Corect
PYTHON
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

Greșit
PYTHON
stoc.sort()
stoc.append(3)
bisect_left(stoc, 3)
Corect
PYTHON
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ă tu

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.

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
3
4
0
Indiciu

Căutarea binară are nevoie de o listă sortată crescător.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.