...
Algoritmi de căutare

Căutarea binară, explicată pas cu pas

Pe scurt

Căutarea binară găsește o valoare într-o listă sortată uitându-se mereu la elementul din mijloc. Dacă e valoarea căutată, gata. Dacă e mai mică, renunță la jumătatea din stânga; dacă e mai mare, la cea din dreapta. Așa, la fiecare pas intervalul se înjumătățește: într-o listă de un milion de elemente găsești orice valoare în cel mult 20 de pași, față de un milion la căutarea pe rând.

  • O(log n)pași pentru n elemente
  • 20de pași pentru 1.000.000 de elemente
  • 1condiție: lista trebuie să fie sortată
  • 2lecții gratuite, fără card
CĂUTARE BINARĂ 2 0 5 1 8 2 12 3 16 4 23 5 38 6 41 7 56 8 st mij dr caut 12: v[4] = 16 > 12 → dr = mij - 1 jumătatea din dreapta e eliminată dintr-un singur pas O(log n) st · mij · dr

Căutarea binară în animație

Scrie numărul căutat și apasă „Pornește”. Indicatorul galben e mijlocul, iar jumătatea eliminată se estompează. La final vezi câți pași ar fi făcut căutarea liniară.

Cum funcționează căutarea binară

Ții două capete: st (stânga) și dr (dreapta), care la început cuprind toată lista. Cât timp st <= dr:

  1. calculezi mijlocul: mij = (st + dr) / 2;
  2. dacă v[mij] este valoarea căutată, ai găsit-o;
  3. dacă v[mij] e mai mic, valoarea poate fi doar în dreapta: st = mij + 1;
  4. altfel poate fi doar în stânga: dr = mij - 1.

Dacă intervalul devine gol (st > dr), valoarea nu există în listă. Exemplu: cauți 12 în [2, 5, 8, 12, 16, 23, 38]. Mijlocul e 12 la poziția 3, deci îl găsești din primul pas. Cauți 23: mijlocul e 12 < 23, treci în dreapta, la [16, 23, 38], mijlocul e 23. Doi pași.

Căutarea binară în C++, Python și Java

Varianta iterativă, cea folosită de obicei, plus varianta recursivă.

def cautare_binara(v, x):
    st, dr = 0, len(v) - 1
    while st <= dr:
        mij = (st + dr) // 2
        if v[mij] == x:
            return mij
        if v[mij] < x:
            st = mij + 1      # x e în dreapta
        else:
            dr = mij - 1      # x e în stânga
    return -1                 # nu există


print(cautare_binara([2, 5, 8, 12, 16, 23, 38], 12))   # 3

Încearcă: scrie tu căutarea binară

Problema din lecția 87 a cursului de algoritmi: cauți și numeri pașii, ca să vezi O(log n) cu ochii tăi.

Exercițiu din lecția 87 · cursul de algoritmi

Căutarea binară

Scrie funcția cautare_binara(lista, x) care caută x într-o listă sortată crescător și returnează tuplul (index, pasi), sau (-1, pasi) dacă x nu există. pasi este numărul de iterații ale buclei while. Nu folosi index() sau operatorul in.

  1. Pornește cu st, dr = 0, len(lista) - 1 și pasi = 0.
  2. În bucla while st <= dr, crește pasi, calculează mijlocul și mută capătul potrivit.
  3. Lista din teste are numerele pare 0, 2, ..., 98. Trebuie să apară: (21, 6), (0, 5), (-1, 6), (-1, 0).
Indiciu: Mijlocul: mij = (st + dr) // 2; capetele se mută la mij + 1 sau mij - 1.
def cautare_binara(lista, x):
    st, dr = 0, len(lista) - 1
    pasi = 0
    while st <= dr:
        pasi += 1
        mij = (st + dr) // 2
        if lista[mij] == x:
            return mij, pasi
        if lista[mij] < x:
            st = mij + 1
        else:
            dr = mij - 1
    return -1, pasi


lista = list(range(0, 100, 2))
print(cautare_binara(lista, 42))
print(cautare_binara(lista, 0))
print(cautare_binara(lista, 51))
print(cautare_binara([], 7))
Începe gratuit cursul de algoritmi →
main.pyPython
ConsolăGata de pornire
Apasă „Rulează codul”. Prima dată Python se încarcă în browser în câteva secunde.

Pe tema asta, în cursul de algoritmi

Pagina îți arată metoda. În curs o aplici singur, pe probleme din ce în ce mai grele, cu verificare automată la fiecare.

Greșeli frecvente

  • Lista nu e sortată. Căutarea binară dă rezultate greșite pe o listă nesortată. Sortezi întâi (O(n log n)) doar dacă faci multe căutări.
  • st < dr în loc de st <= dr. Ratezi cazul în care intervalul are un singur element.
  • st = mij în loc de st = mij + 1. Intervalul nu se mai micșorează și bucla devine infinită.
  • Depășirea la numere mari. În C++ și Java, (st + dr) / 2 poate depăși int; scrie st + (dr - st) / 2.

Variante care apar la interviuri

Ideea de bază se folosește în multe probleme: prima și ultima poziție a unei valori (echivalentul lui lower_bound și upper_bound din C++, sau bisect din Python), rădăcina pătrată întreagă și căutarea binară pe răspuns, unde cauți cea mai mică valoare care respectă o condiție. La BAC, căutarea binară apare în vectori sortați și se cere des explicit „un algoritm eficient”.

4,9 din 5 · 128 de recenzii Google

Ce spun cursanții

Toate recenziile pe Google
Video · 13 minute

Absolvenții noștri, în cuvintele lor

Cursanți care au pornit de la zero povestesc cum au învățat, ce i-a ajutat și unde au ajuns după cursuri.

Vezi pe YouTube

Am participat la primul modul de programare in Java, cel pentru incepatori si am fost placut impresionat de structura cursului. Am remarcat aspectul concret al cursului, bine dozat pentru fiecare sedinta, iar temele de studiu propuse au fost finalizate de fiecare data. Conceptul cursului este logic, trainerul fiind atent si intreband de fiecare data in timpul si la finalul fiecarei sedinte daca s-a inteles sau daca participantii au intrebari, explicatiile fiind concrete si la obiect. Personal am o experienta vasta in training si sisteme de learning in alte domenii atat in tara cat si in strainatae si recomand frecventarea cursurilor la Academia Programatorilor.

Fotografia lui Cristescu Ovidiu, cursant al Academiei ProgramatorilorCristescu OvidiuRecenzie pe Google

Recomand orice curs predat la Academia Programatorilor, indiferent ca vrei sa inveti singur sau cu alti colegi in grupa. Totul este explicat in asa fel incat sa intelegi. Eu am inceput Java incepator cu colegi de grupa, dar am vrut sa ma axez mai mult pe C# (one to one), deoarece folosesc mai mult acest limbaj la serviciu. M-a ajutat foarte mult sa inteleg si sa pun in practica din ce am invatat.

Fotografia lui Diana Badea, cursant al Academiei ProgramatorilorDiana BadeaRecenzie pe Google

Recomand cu căldură Academia pentru orice tânăr care dorește sa înceapă o carieră în IT. Aici nu găsești un profesor care sa îți predea o materie și atât, aici găsești un om care pe lângă faptul ca îți explica fiecare parte a programării intr-un mod practic, poți afla de la el și cum ar decurge o zi din viata ta la job, ceea ce a făcut el ca să ajungă în acest punct și toate experientele sale, un lucru de milioane.

Fotografia lui Daniel Marian, cursant al Academiei ProgramatorilorDaniel MarianRecenzie pe Google

Întrebări frecvente

Ce este căutarea binară?

Căutarea binară este un algoritm care găsește poziția unei valori într-o listă sortată. Compară valoarea cu elementul din mijloc și, în funcție de rezultat, continuă doar în jumătatea stângă sau doar în cea dreaptă, până găsește valoarea sau intervalul devine gol.

Care este complexitatea căutării binare?

O(log n), pentru că la fiecare pas numărul de elemente rămase se înjumătățește. Pentru 1.000 de elemente face cel mult 10 pași, iar pentru 1.000.000 cel mult 20. Memoria suplimentară este O(1) în varianta iterativă și O(log n) în cea recursivă.

De ce trebuie lista să fie sortată?

Pentru că algoritmul decide în ce jumătate să caute comparând cu mijlocul. Doar într-o listă sortată știi sigur că toate elementele din stânga mijlocului sunt mai mici și cele din dreapta sunt mai mari.

Care e diferența dintre căutarea liniară și căutarea binară?

Căutarea liniară verifică elementele pe rând și merge pe orice listă, în O(n). Căutarea binară cere o listă sortată, dar e mult mai rapidă: O(log n).

Există căutare binară gata făcută?

Da: în C++ ai binary_search, lower_bound și upper_bound în <algorithm>, în Python modulul bisect, iar în Java Arrays.binarySearch și Collections.binarySearch. La BAC și la interviuri ți se cere de obicei să o scrii singur.

Unde exersez căutarea binară?

În cursul de algoritmi pentru interviuri de la Academia Programatorilor ai 5 lecții de căutare binară, cu probleme pe care le rezolvi în Python direct în browser. Primele 2 lecții ale cursului sunt gratuite.

Începe azi, gratuit

Primele lecții din fiecare curs sunt gratuite. Fără card, fără instalări: scrii primul cod în câteva minute.