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

Căutarea binară nu găsește elementul de la capăt (while stanga < dreapta)

Pe scurt

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

Greșit
PYTHON
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 -1
Corect
PYTHON
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 -1

Cu <= 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ă

Greșit
PYTHON
while stanga < dreapta:
    m = (stanga + dreapta) // 2
    if v[m] < x:
        stanga = m + 1
    else:
        dreapta = m
return -1
Corect
PYTHON
while 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 -1

Varianta cu while stanga < dreapta și dreapta = m e corectă, dar se termină cu un singur candidat, care trebuie verificat după buclă.

Repară tu

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.

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

Când stanga == dreapta mai există un candidat care trebuie comparat.

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

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