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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
În varianta „căutare exactă” intervalul [stanga, dreapta] conține toți candidații care n-au fost verificați. Când stanga == dreapta, mai există exact un candidat. Condiția while stanga < dreapta oprește bucla tocmai atunci, fără să compare acel ultim element.
Rezultatul: funcția returnează „nu există” pentru valori care sunt în listă, de obicei pentru primul sau ultimul element, sau pentru o listă cu un singur element. Python nu dă nicio eroare, e un bug off-by-one. În „Repară tu” testele cu assert arată valoarea greșită.
Regula de verificare: condiția buclei trebuie să fie adevărată cât timp intervalul mai conține cel puțin un candidat. La intervalul închis, intervalul e nevid cât timp stanga <= dreapta.
De ce apare: cauzele frecvente
1Condiția buclei exclude ultimul candidat
stanga, dreapta = 0, len(v) - 1
while stanga < dreapta:
m = (stanga + dreapta) // 2
if v[m] == x:
return m
if v[m] < x:
stanga = m + 1
else:
dreapta = m - 1
return -1stanga, dreapta = 0, len(v) - 1
while stanga <= dreapta:
m = (stanga + dreapta) // 2
if v[m] == x:
return m
if v[m] < x:
stanga = m + 1
else:
dreapta = m - 1
return -1Cu <= bucla mai face un pas când a rămas un singur element și îl compară. Intervalul devine gol abia când stanga > dreapta.
2Returnezi -1 fără să verifici poziția finală
while stanga < dreapta:
m = (stanga + dreapta) // 2
if v[m] < x:
stanga = m + 1
else:
dreapta = m
return -1while stanga < dreapta:
m = (stanga + dreapta) // 2
if v[m] < x:
stanga = m + 1
else:
dreapta = m
return stanga if v and v[stanga] == x else -1Varianta cu while stanga < dreapta și dreapta = m e corectă, dar se termină cu un singur candidat, care trebuie verificat după buclă.
Repară eroarea, direct în pagină
Funcția pozitie_cod(coduri, x) caută binar un cod într-o listă sortată, dar testele cu assert pică: codurile de la capete și lista cu un element dau -1. Repar-o ca testele să treacă și să afișeze 0 4 0 -1.
def pozitie_cod(coduri, x):
stanga, dreapta = 0, len(coduri) - 1
while stanga < dreapta:
m = (stanga + dreapta) // 2
if coduri[m] == x:
return m
if coduri[m] < x:
stanga = m + 1
else:
dreapta = m - 1
return -1
v = [101, 205, 310, 420, 555]
rez = (pozitie_cod(v, 101), pozitie_cod(v, 555), pozitie_cod([77], 77), pozitie_cod(v, 300))
assert rez == (0, 4, 0, -1), f"pozitii gresite: {rez}"
print(*rez)0 4 0 -1
Indiciu
Când stanga == dreapta mai există un candidat care trebuie comparat.
Reparația
def pozitie_cod(coduri, x):
stanga, dreapta = 0, len(coduri) - 1
while stanga <= dreapta:
m = (stanga + dreapta) // 2
if coduri[m] == x:
return m
if coduri[m] < x:
stanga = m + 1
else:
dreapta = m - 1
return -1
v = [101, 205, 310, 420, 555]
rez = (pozitie_cod(v, 101), pozitie_cod(v, 555), pozitie_cod([77], 77), pozitie_cod(v, 300))
assert rez == (0, 4, 0, -1), f"pozitii gresite: {rez}"
print(*rez)De ce merge
Căutând 101, intervalul se reduce la [0, 0]. Cu while stanga < dreapta bucla se oprea aici fără să compare coduri[0] și returna -1. La lista [77] bucla nici nu începea. Cu <=, bucla mai face exact un pas cu singurul candidat rămas și îl găsește. Pentru 300, intervalul devine gol (stanga > dreapta), deci funcția returnează corect -1.
Cum o eviți pe viitor
Testează orice căutare binară pe: primul element, ultimul element, lista cu un singur element (găsit și negăsit) și o valoare care lipsește. Folosește un singur șablon pe care îl știi pe de rost și ține minte perechea: [stanga, dreapta] merge cu while stanga <= dreapta, [stanga, dreapta) merge cu while stanga < dreapta.
Întrebări frecvente
De ce găsește elementele din mijloc, dar nu pe cele de la capete?
Elementele din mijloc sunt comparate devreme, cât intervalul e încă mare. Cele de la capete rămân ultimele candidate, adică exact cazul stanga == dreapta pe care bucla îl sare.
Se poate ajunge și la buclă infinită cu aceeași greșeală?
Nu cu mijloc + 1 și mijloc - 1: intervalul scade mereu. Bucla infinită apare când combini <= cu dreapta = mijloc sau scrii stanga = mijloc.
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. 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. Fereastra glisantă sare peste ultima fereastră (off-by-one la range) O listă cu n elemente are n - k + 1 ferestre de lungime k, deci bucla trebuie să fie range(len(lista) - k + 1). Cu range(len(lista) - k) ultima fereastră nu e verificată, iar rezultatul e greșit fără nicio eroare. Î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.
