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.
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
while stanga <= dreapta:
mijloc = (stanga + dreapta) // 2
if lista[mijloc] == x:
return mijloc
if lista[mijloc] < x:
stanga = mijloc
else:
dreapta = mijlocwhile stanga <= dreapta:
mijloc = (stanga + dreapta) // 2
if lista[mijloc] == x:
return mijloc
if lista[mijloc] < x:
stanga = mijloc + 1
else:
dreapta = mijloc - 1Elementul 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
while stanga <= dreapta:
mijloc = (stanga + dreapta) // 2
if lista[mijloc] >= x:
dreapta = mijloc
else:
stanga = mijloc + 1while stanga < dreapta:
mijloc = (stanga + dreapta) // 2
if lista[mijloc] >= x:
dreapta = mijloc
else:
stanga = mijloc + 1Câ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ă 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.
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))3 0 -1
Indiciu
Elementul de pe mijloc a fost deja comparat: capătul nou trebuie să-l excludă.
Reparația
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 + 1
else:
dreapta = mijloc - 1
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))De ce merge
Căutând 33, intervalul ajungea la [2, 3]: mijlocul e 2, valoarea 19 e mai mică, iar stanga = mijloc lăsa stanga tot pe 2, deci bucla se repeta la nesfârșit. Cu stanga = mijloc + 1 și dreapta = mijloc - 1, elementul deja comparat iese din interval, iar intervalul scade la fiecare pas. Pentru 40, intervalul devine gol (stanga > dreapta), bucla se termină și funcția returnează -1.
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, cumijloc + 1/mijloc - 1; - prima poziție care îndeplinește o condiție:
while stanga < dreapta, cudreapta = 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
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. Căutarea binară nu găsește elementul de la capăt (while stanga < dreapta) Ai folosit while stanga < dreapta cu intervalul închis [0, len - 1] și actualizări mijloc + 1 / mijloc - 1. Bucla se oprește când rămâne un singur element, fără să-l verifice, deci returnează -1 deși valoarea există. Folosește while stanga <= dreapta. Parcurgerea listei înlănțuite nu se mai oprește (lipsește curent = curent.urm) În bucla while curent: ai uitat să avansezi cu curent = curent.urm (sau avansezi doar pe o ramură a unui if), așa că nodul curent nu se schimbă și bucla rulează la nesfârșit; editorul o oprește după limita de timp. Avansează pe fiecare drum prin buclă. Î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.
