IndexError: list index out of range la căutarea binară
Ai pornit căutarea binară cu dreapta = len(lista) și bucla while stanga <= dreapta, așa că mijlocul poate ajunge la len(lista), o poziție care nu există. Cu <= pornește de la dreapta = len(lista) - 1.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Există două convenții corecte pentru căutarea binară: interval închis [stanga, dreapta], cu dreapta = len(lista) - 1 și while stanga <= dreapta, și interval semideschis [stanga, dreapta), cu dreapta = len(lista) și while stanga < dreapta. Eroarea apare când le amesteci: pornești cu dreapta = len(lista) (semideschis), dar scrii while stanga <= dreapta (închis).
Cât timp elementul căutat e în interiorul listei, totul pare corect. Când cauți o valoare mai mare decât toate, stanga crește până ajunge la len(lista), mijlocul devine len(lista), iar lista[mijloc] iese din listă.
Pe lista goală, aceeași combinație pică imediat: stanga = dreapta = 0 și lista[0] nu există. Testează mereu valoarea mai mare decât toate și lista goală.
De ce apare: cauzele frecvente
1Convenții amestecate
stanga, dreapta = 0, len(lista)
while stanga <= dreapta:
mijloc = (stanga + dreapta) // 2
if lista[mijloc] < x:
stanga = mijloc + 1
else:
dreapta = mijloc - 1stanga, dreapta = 0, len(lista) - 1
while stanga <= dreapta:
mijloc = (stanga + dreapta) // 2
if lista[mijloc] < x:
stanga = mijloc + 1
else:
dreapta = mijloc - 1În intervalul închis, dreapta este ultimul indice care poate fi citit, deci trebuie să fie len(lista) - 1.
2Citești lista după buclă fără să verifici poziția
poz = cauta_prima_mai_mare(lista, x)
print(lista[poz])poz = cauta_prima_mai_mare(lista, x)
if poz < len(lista):
print(lista[poz])Căutările de tip „poziția de inserare” pot returna len(lista), care înseamnă „după ultimul element”. Verifică înainte să citești.
Repară eroarea, direct în pagină
Funcția exista_nota(note, x) verifică binar dacă o notă apare în catalogul sortat. Pe nota mai mare decât toate și pe catalogul gol dă IndexError: list index out of range. Repar-o ca să afișeze True, False și False.
def exista_nota(note, x):
stanga, dreapta = 0, len(note)
while stanga <= dreapta:
mijloc = (stanga + dreapta) // 2
if note[mijloc] == x:
return True
if note[mijloc] < x:
stanga = mijloc + 1
else:
dreapta = mijloc - 1
return False
print(exista_nota([4, 6, 7, 9, 10], 9))
print(exista_nota([4, 6, 7, 9, 10], 11))
print(exista_nota([], 5))True False False
Indiciu
Cu bucla while stanga <= dreapta, dreapta trebuie să fie ultimul indice valid.
Reparația
def exista_nota(note, x):
stanga, dreapta = 0, len(note) - 1
while stanga <= dreapta:
mijloc = (stanga + dreapta) // 2
if note[mijloc] == x:
return True
if note[mijloc] < x:
stanga = mijloc + 1
else:
dreapta = mijloc - 1
return False
print(exista_nota([4, 6, 7, 9, 10], 9))
print(exista_nota([4, 6, 7, 9, 10], 11))
print(exista_nota([], 5))De ce merge
Bucla while stanga <= dreapta citește și poziția dreapta, deci dreapta trebuie să fie un indice valid: len(note) - 1. Codul stricat pornea de la len(note): căutând 11, stanga ajungea la 5 și se citea note[5], care nu există; pe catalogul gol se citea note[0]. După reparație, intervalul devine gol (stanga > dreapta) înainte de orice acces în afara listei.
Alte forme ale mesajului
IndexError: list index out of range
Cum o eviți pe viitor
Scrie în comentariu ce convenție folosești: # interval [stanga, dreapta] sau # interval [stanga, dreapta), și păstrează-o în toată funcția: inițializarea, condiția buclei și actualizările. Testează patru cazuri: valoarea la început, la final, mai mare decât toate și lista goală. Pentru inserări și căutări de poziție, modulul bisect (bisect_left, bisect_right) evită complet aceste erori.
Întrebări frecvente
Care convenție e mai bună?
Amândouă sunt corecte. Intervalul închis e mai ușor pentru căutarea exactă, iar cel semideschis e mai natural pentru „prima poziție cu proprietatea X”, care poate fi și len(lista). Important e să nu le amesteci.
De ce (stanga + dreapta) // 2 și nu (stanga + dreapta) / 2?
Operatorul / dă un număr zecimal (2.5), iar indicii trebuie să fie întregi. // este împărțirea întreagă. Cu / primești TypeError: list indices must be integers or slices, not float.
Erori înrudite
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. TypeError: list indices must be integers or slices, not float Ai calculat poziția cu împărțirea obișnuită /, care dă mereu un număr zecimal (2.0, 2.5), iar indicii de listă trebuie să fie întregi. Folosește împărțirea întreagă: mijloc = (stanga + dreapta) // 2. IndexError: list index out of range la două pointere Pointerul din dreapta a pornit de la len(lista) în loc de len(lista) - 1, sau unul din pointeri a ieșit din listă fără ca bucla să se oprească. Pornește cu dreapta = len(lista) - 1 și pune condiția stanga < dreapta în while. Î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.
