Algoritm de căutare binar cu EXEMPLU

Înainte de a învăța căutarea binară, haideți să învățăm ce este căutarea.

Ce este Căutarea?

Căutarea este un utilitar care îi permite utilizatorului să găsească documente, fișiere, media sau orice alt tip de date deținute într-o bază de date. Căutarea funcționează pe principiul simplu de potrivire a criteriilor cu înregistrările și afișarea acestuia către utilizator. În acest fel funcționează cea mai simplă funcție de căutare.

Ce este căutarea binară?

O căutare binară este un tip avansat de algoritm de căutare care găsește și preia date dintr-o listă sortată de elemente. Principiul său de funcționare de bază implică împărțirea datelor din listă în jumătate până când valoarea necesară este localizată și afișată utilizatorului în rezultatul căutării. Căutarea binară este cunoscută în mod obișnuit ca... căutare pe jumătate de interval sau un căutare logaritmică.

Cum funcționează căutarea binară?

Căutarea binară funcționează în felul următor:

• Procesul de căutare inițiază prin localizarea elementului din mijloc al matricei de date sortate.
• După aceea, valoarea cheii este comparată cu elementul.
• Dacă valoarea cheii este mai mică decât elementul din mijloc, atunci căutarea analizează valorile superioare elementului din mijloc pentru comparație și potrivire.
• În cazul în care valoarea cheii este mai mare decât elementul din mijloc, atunci căutarea analizează valorile mai mici decât elementul din mijloc pentru comparație și potrivire.

Algoritmul de căutare binară (pseudocod)

Căutarea binară poate fi scrisă ca o rutină scurtă, iterativă. Păstrează doi pointeri, low și high, și restrânge intervalul până când ținta este găsită sau intervalul devine gol.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Rutina returnează indexul țintei în caz de succes și -1 când valoarea nu este prezentă. Deoarece intervalul se înjumătățește la fiecare trecere, bucla rulează de cel mult log₂(n) ori.

Exemplu de căutare binară

Să ne uităm la exemplul unui dicționar. Dacă trebuie să găsiți un anumit cuvânt, nimeni nu parcurge fiecare cuvânt într-o manieră secvențială, ci localizează aleatoriu cuvintele cele mai apropiate pentru a căuta cuvântul dorit.

Imaginea de mai sus ilustrează următoarele:

1. Aveți o matrice de 10 cifre, iar elementul 59 trebuie găsit.
2. Toate elementele sunt marcate cu indicele de la 0 la 9. Acum, se calculează mijlocul matricei. Pentru a face acest lucru, luați valorile din stânga și din dreapta indicelui și le împărțiți la 2. Rezultatul este 4.5, dar luăm valoarea minimă. Prin urmare, mijlocul este 4.
3. Algoritmul elimină toate elementele de la mijloc (4) la limita inferioară, deoarece 59 este mai mare decât 24, iar acum matricea rămâne cu doar 5 elemente.
4. Acum, 59 este mai mare decât 45 și mai mic decât 63. Mijlocul este 7. Prin urmare, valoarea indicelui din dreapta devine mijloc − 1, ceea ce este egal cu 6, iar valoarea indicelui din stânga rămâne aceeași ca înainte, adică 5.
5. În acest moment, știți că 59 vine după 45. Prin urmare, indicele din stânga, care este 5, devine și el la mijloc.
6. Aceste iterații continuă până când matricea este redusă la un singur element sau elementul care trebuie găsit devine mijlocul matricei.

Exemplu 2

Să analizăm următorul exemplu pentru a înțelege cum funcționează căutarea binară.

1. Aveți o serie de valori sortate de la 2 la 20 și trebuie să găsiți 18.
2. Media limitelor inferioară și superioară este (l + r) / 2 = 4. Valoarea căutată este mai mare decât valoarea medie, care este 4.
3. Valorile matricei mai mici decât valoarea medie sunt eliminate din căutare, iar valorile mai mari decât valoarea medie 4 sunt căutate.
4. Acesta este un proces de împărțire recurent până când este găsit elementul care trebuie căutat.

De ce avem nevoie de căutare binară?

Următoarele motive fac ca căutarea binară să fie o alegere mai bună pentru a fi utilizată ca algoritm de căutare:

• Căutarea binară funcționează eficient asupra datelor sortate, indiferent de dimensiunea acestora.
• În loc să efectueze căutarea parcurgând datele într-o secvență, algoritmul binar accesează aleatoriu datele pentru a găsi elementul necesar. Acest lucru face ca ciclurile de căutare să fie mai scurte și mai precise.
• Căutarea binară efectuează comparații ale datelor sortate pe baza unui principiu de ordonare, mai degrabă decât utilizând comparații de egalitate, care sunt mai lente și în mare parte inexacte.
• După fiecare ciclu de căutare, algoritmul împarte dimensiunea tabloului la jumătate; prin urmare, în următoarea iterație, va funcționa doar în jumătatea rămasă a tabloului.

Află următorul nostru tutorial despre Căutare liniară: Python, C++ Exemplu.

Căutare binară vs. căutare liniară

Căutarea binară și căutarea liniară sunt cele mai comune două metode de a găsi o valoare într-o colecție. Tabelul de mai jos evidențiază diferențele dintre ele:

Pe scurt, căutarea binară este mult mai rapidă pe date sortate de dimensiuni mari, în timp ce căutarea liniară este mai simplă și singura opțiune atunci când datele nu sunt sortate.

Întrebări frecvente