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

Căutarea binară returnează o apariție oarecare, nu prima, când valoarea se repetă

Pe scurt

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

Greșit
PYTHON
if nums[mij] == x:
    return mij
Corect
PYTHON
if nums[mij] == x:
    rez = mij
    dr = mij - 1

Reț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ă

Greșit
PYTHON
if nums[mij] == x:
    rez = mij
    dr = mij - 1
Corect
PYTHON
if nums[mij] == x:
    rez = mij
    st = mij + 1

Pentru ultima apariție cauți în dreapta după fiecare potrivire.

3Alternativa din biblioteca standard

Greșit
PYTHON
i = nums.index(x)
Corect
PYTHON
from bisect import bisect_left
i = bisect_left(nums, x)
if i == len(nums) or nums[i] != x:
    i = -1

nums.index e corect, dar O(n). bisect_left dă prima apariție în O(log n).

Repară tu

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.

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

La egalitate, salvează mij într-o variabilă și continuă cu dr = mij - 1.

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

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