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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Tehnica două pointere folosește doi indici, de obicei unul la început (stanga = 0) și unul la final, care se apropie unul de altul. Ultimul element al unei liste are indicele len(lista) - 1. Dacă pornești cu dreapta = len(lista), chiar primul acces lista[dreapta] cere un element care nu există.
A doua cauză frecventă: un pointer avansează într-o buclă interioară (de exemplu sari peste duplicate sau peste caractere care nu sunt litere) fără să verifici că a rămas în listă. Pe date obișnuite merge, dar pe un caz limită (toate elementele identice, text doar cu spații) pointerul iese din listă.
Linia din mesaj îți arată accesul greșit. Afișează stanga și dreapta înainte de linia respectivă: vei vedea imediat care dintre ei a ajuns la len(lista) sau mai departe.
De ce apare: cauzele frecvente
1Pointerul din dreapta pornește de la len(lista)
def pereche(lista, tinta):
stanga, dreapta = 0, len(lista)
while stanga < dreapta:
s = lista[stanga] + lista[dreapta]
if s == tinta:
return (stanga, dreapta)
if s < tinta:
stanga += 1
else:
dreapta -= 1def pereche(lista, tinta):
stanga, dreapta = 0, len(lista) - 1
while stanga < dreapta:
s = lista[stanga] + lista[dreapta]
if s == tinta:
return (stanga, dreapta)
if s < tinta:
stanga += 1
else:
dreapta -= 1Ultimul indice valid este len(lista) - 1. Cu len(lista) primul acces la lista[dreapta] iese deja din listă.
2Bucla interioară nu verifică limita
while text[stanga] == ' ':
stanga += 1while stanga < dreapta and text[stanga] == ' ':
stanga += 1Pe un text format doar din spații, prima variantă trece de capăt. Condiția de limită trebuie verificată înainte de acces, iar and se oprește la prima condiție falsă.
Repară eroarea, direct în pagină
Funcția pereche_buget(preturi, buget) caută într-o listă sortată două prețuri care dau exact bugetul și returnează pozițiile lor (sau None). Codul dă IndexError: list index out of range. Repar-o ca să afișeze (1, 3), None și None.
def pereche_buget(preturi, buget):
stanga, dreapta = 0, len(preturi)
while stanga < dreapta:
s = preturi[stanga] + preturi[dreapta]
if s == buget:
return (stanga, dreapta)
if s < buget:
stanga += 1
else:
dreapta -= 1
return None
print(pereche_buget([10, 20, 35, 50, 80], 70))
print(pereche_buget([10, 20], 100))
print(pereche_buget([], 5))(1, 3) None None
Indiciu
Verifică de unde pornește pointerul din dreapta.
Reparația
def pereche_buget(preturi, buget):
stanga, dreapta = 0, len(preturi) - 1
while stanga < dreapta:
s = preturi[stanga] + preturi[dreapta]
if s == buget:
return (stanga, dreapta)
if s < buget:
stanga += 1
else:
dreapta -= 1
return None
print(pereche_buget([10, 20, 35, 50, 80], 70))
print(pereche_buget([10, 20], 100))
print(pereche_buget([], 5))De ce merge
Pointerul din dreapta trebuie să arate spre ultimul element, iar ultimul indice valid este len(preturi) - 1. Codul stricat pornea de la len(preturi) și cerea un element care nu există chiar la primul pas. După reparație, suma 10 + 80 e prea mare, deci dreapta scade; 10 + 50 e prea mică, deci stanga crește; 20 + 50 = 70, pozițiile 1 și 3. La lista goală, dreapta este -1, iar while 0 < -1 nu rulează deloc.
Alte forme ale mesajului
IndexError: list index out of rangeIndexError: string index out of range
Cum o eviți pe viitor
La două pointere scrie de la început perechea standard: stanga, dreapta = 0, len(lista) - 1 și while stanga < dreapta. Orice buclă interioară care mută un pointer primește aceeași condiție de limită ca bucla principală, pusă prima în and. Testează pe lista goală, pe o listă cu un element și pe una cu toate elementele egale.
Întrebări frecvente
Când folosesc stanga < dreapta și când stanga <= dreapta?
Cu < te oprești când pointerii se întâlnesc: potrivit pentru perechi sau palindromuri, unde elementul din mijloc nu are pereche. Cu <= procesezi și elementul unde se întâlnesc, cum faci la căutarea binară.
De ce eroarea apare doar pe unele teste?
Pointerul iese din listă doar dacă ajunge la capăt, ceea ce se întâmplă pe cazurile limită. Pe datele obișnuite bucla se oprește mai devreme.
Erori înrudite
IndexError: list index out of range la lista[i + 1] Compari fiecare element cu următorul (lista[i] și lista[i + 1]), dar bucla merge până la ultimul element, care nu are un următor. Oprește bucla cu un pas mai devreme: for i in range(len(lista) - 1). 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. Î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.
