Căutarea binară returnează o apariție oarecare, nu prima, când valoarea se repetă
Căutarea binară clasică se oprește la prima potrivire întâlnită, care poate fi oricare dintre valorile egale. Ca să găsești prima apariție, când nums[mijloc] == x salvează poziția și continuă căutarea în stânga (dreapta = mijloc - 1).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Varianta din manuale a căutării binare răspunde la întrebarea „există x în listă?”: când găsește valoarea, returnează imediat poziția. Dacă lista are mai multe valori egale, poziția returnată depinde doar de unde cade mijlocul, nu de unde începe secvența.
Multe probleme cer însă prima sau ultima apariție: prima versiune defectă, prima zi cu un anumit stoc, primul index de inserare. Pentru ele, la egalitate nu te oprești: reții poziția ca un candidat și restrângi căutarea în partea stângă (pentru prima apariție) sau în cea dreaptă (pentru ultima).
Nu primești nicio eroare, iar pe liste fără duplicate rezultatul e corect, de aceea greșeala scapă ușor la testele simple.
De ce apare: cauzele frecvente
1return imediat la egalitate
if nums[mij] == x:
return mijif nums[mij] == x:
rez = mij
dr = mij - 1Reții poziția găsită și cauți în continuare în stânga, unde ar putea fi o apariție mai devreme. La final, rez e prima apariție.
2Ultima apariție cu aceeași logică
if nums[mij] == x:
rez = mij
dr = mij - 1if nums[mij] == x:
rez = mij
st = mij + 1Pentru ultima apariție cauți în dreapta după fiecare potrivire.
3Alternativa din biblioteca standard
i = nums.index(x)from bisect import bisect_left
i = bisect_left(nums, x)
if i == len(nums) or nums[i] != x:
i = -1nums.index e corect, dar O(n). bisect_left dă prima apariție în O(log n).
Repară eroarea, direct în pagină
Funcția prima_zi(stoc, x) trebuie să returneze prima zi (indexul) în care stocul, sortat crescător, are valoarea x, sau -1. Testul cu assert pică: pentru valoarea 2 returnează altă zi decât prima. Repar-o ca să afișeze 1, 6 și -1.
def prima_zi(stoc, x):
st, dr = 0, len(stoc) - 1
while st <= dr:
mij = (st + dr) // 2
if stoc[mij] == x:
return mij
if stoc[mij] < x:
st = mij + 1
else:
dr = mij - 1
return -1
stoc = [1, 2, 2, 2, 2, 3, 5]
for x, corect in [(2, 1), (5, 6), (4, -1)]:
rez = prima_zi(stoc, x)
assert rez == corect, f'pozitie gresita: {rez} in loc de {corect}'
print(rez)1 6 -1
Indiciu
La egalitate, salvează mij într-o variabilă și continuă cu dr = mij - 1.
Reparația
def prima_zi(stoc, x):
st, dr = 0, len(stoc) - 1
rez = -1
while st <= dr:
mij = (st + dr) // 2
if stoc[mij] == x:
rez = mij
dr = mij - 1
elif stoc[mij] < x:
st = mij + 1
else:
dr = mij - 1
return rez
stoc = [1, 2, 2, 2, 2, 3, 5]
for x, corect in [(2, 1), (5, 6), (4, -1)]:
rez = prima_zi(stoc, x)
assert rez == corect, f'pozitie gresita: {rez} in loc de {corect}'
print(rez)De ce merge
Primul mijloc e indexul 3, unde stocul e deja 2, așa că varianta veche returna 3. Acum poziția 3 devine doar un candidat, iar căutarea continuă între 0 și 2: găsește 2 și la indexul 1, care devine noul candidat, apoi verifică indexul 0 (valoarea 1) și se oprește. Rezultatul e prima apariție, tot în O(log n).
Cum o eviți pe viitor
Înainte să scrii căutarea binară, decide ce returnează: orice poziție, prima apariție, ultima apariție sau primul element mai mare. Pentru prima/ultima, folosește tiparul „reține candidatul și continuă” sau bisect_left / bisect_right. Testează pe o listă în care valoarea căutată apare de cel puțin trei ori, la mijloc.
Întrebări frecvente
Complexitatea rămâne O(log n)?
Da. Faci în continuare câte o înjumătățire la fiecare pas, doar că nu te oprești mai devreme.
Pot găsi o apariție și apoi să merg spre stânga cu o buclă?
Merge, dar dacă valoarea se repetă de un milion de ori, bucla e O(n). Varianta binară rămâne O(log n) mereu.
Erori înrudite
bisect_left în loc de bisect_right: numărul de valori dintr-un interval iese prea mic bisect_left(lista, b) dă poziția dinaintea primei apariții a lui b, deci valorile egale cu b nu sunt numărate. Pentru câte valori sunt în intervalul [a, b] folosește bisect_right(lista, b) - bisect_left(lista, a). 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. 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. Î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.
