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

IndexError: list index out of range la căutarea binară

Pe scurt

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

Greșit
PYTHON
stanga, dreapta = 0, len(lista)
while stanga <= dreapta:
    mijloc = (stanga + dreapta) // 2
    if lista[mijloc] < x:
        stanga = mijloc + 1
    else:
        dreapta = mijloc - 1
Corect
PYTHON
stanga, 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

Greșit
PYTHON
poz = cauta_prima_mai_mare(lista, x)
print(lista[poz])
Corect
PYTHON
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ă tu

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.

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

Cu bucla while stanga <= dreapta, dreapta trebuie să fie ultimul indice valid.

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

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