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

Căutarea binară intră în buclă infinită (stanga = mijloc)

Pe scurt

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.

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

Căutarea binară funcționează pentru că, la fiecare pas, intervalul [stanga, dreapta] se înjumătățește. Dacă scrii stanga = mijloc în loc de stanga = mijloc + 1, există o situație în care intervalul nu se mai schimbă: când stanga și dreapta sunt alăturate, mijloc = (stanga + dreapta) // 2 este egal cu stanga, deci stanga = mijloc nu mută nimic. Bucla rulează la nesfârșit.

Python nu dă o excepție pentru o buclă infinită. În editorul nostru programul e oprit după limita de timp, cu mesajul „Programul a rulat prea mult și a fost oprit”. Pe calculatorul tău programul pare doar „blocat”.

Regula: elementul de pe mijloc a fost deja verificat, deci nu trebuie să rămână în interval. Cu while stanga <= dreapta folosește mijloc + 1 și mijloc - 1. Cu varianta while stanga < dreapta (pentru prima poziție care îndeplinește o condiție), folosește dreapta = mijloc și stanga = mijloc + 1.

De ce apare: cauzele frecvente

1stanga = mijloc

Greșit
PYTHON
while stanga <= dreapta:
    mijloc = (stanga + dreapta) // 2
    if lista[mijloc] == x:
        return mijloc
    if lista[mijloc] < x:
        stanga = mijloc
    else:
        dreapta = mijloc
Corect
PYTHON
while stanga <= dreapta:
    mijloc = (stanga + dreapta) // 2
    if lista[mijloc] == x:
        return mijloc
    if lista[mijloc] < x:
        stanga = mijloc + 1
    else:
        dreapta = mijloc - 1

Elementul de pe mijloc a fost comparat, deci intervalul următor trebuie să-l excludă. Așa intervalul scade cu cel puțin 1 la fiecare pas.

2dreapta = mijloc împreună cu while stanga <= dreapta

Greșit
PYTHON
while stanga <= dreapta:
    mijloc = (stanga + dreapta) // 2
    if lista[mijloc] >= x:
        dreapta = mijloc
    else:
        stanga = mijloc + 1
Corect
PYTHON
while stanga < dreapta:
    mijloc = (stanga + dreapta) // 2
    if lista[mijloc] >= x:
        dreapta = mijloc
    else:
        stanga = mijloc + 1

Când stanga == dreapta, mijloc e același, iar dreapta = mijloc nu schimbă nimic. Varianta cu dreapta = mijloc se folosește cu while stanga < dreapta.

Repară tu

Repară eroarea, direct în pagină

Funcția cauta_pret(preturi, x) caută binar un preț într-o listă sortată și returnează poziția lui (sau -1). Programul nu se termină și e oprit după limita de timp. Repar-o ca să afișeze 3, 0 și -1.

Codul care dă eroarea
PYTHON
def cauta_pret(preturi, x):
    stanga, dreapta = 0, len(preturi) - 1
    while stanga <= dreapta:
        mijloc = (stanga + dreapta) // 2
        if preturi[mijloc] == x:
            return mijloc
        if preturi[mijloc] < x:
            stanga = mijloc
        else:
            dreapta = mijloc
    return -1

print(cauta_pret([5, 12, 19, 33, 47], 33))
print(cauta_pret([5, 12, 19, 33, 47], 5))
print(cauta_pret([5, 12, 19, 33, 47], 40))
După reparație, programul afișează
3
0
-1
Indiciu

Elementul de pe mijloc a fost deja comparat: capătul nou trebuie să-l excludă.

Alte forme ale mesajului

  • Programul a rulat prea mult și a fost oprit. Verifică dacă ai o buclă infinită.

Cum o eviți pe viitor

Alege un singur șablon de căutare binară și folosește-l mereu:

  • căutare exactă: while stanga <= dreapta, cu mijloc + 1 / mijloc - 1;
  • prima poziție care îndeplinește o condiție: while stanga < dreapta, cu dreapta = mijloc / stanga = mijloc + 1.

Verifică manual cazul cu două elemente (stanga = 0, dreapta = 1): după fiecare ramură, intervalul trebuie să devină mai mic.

Întrebări frecvente

De ce funcționează pe unele teste și pe altele se blochează?

Bucla se blochează doar când intervalul ajunge la două elemente alăturate și se intră pe ramura cu stanga = mijloc. Dacă elementul e găsit înainte, funcția returnează normal.

Pe calculatorul meu nu apare niciun mesaj. Cum îmi dau seama?

Un program care nu se termină și nu afișează nimic este semnul unei bucle infinite. Oprește-l cu Ctrl+C: Python afișează KeyboardInterrupt și linia la care se afla, de obicei chiar bucla while.

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.