Algoritm de căutare binar cu EXEMPLU

Înainte de a învăța căutarea binară, să învățăm:

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 articole. Principiul său de lucru de bază implică împărțirea datelor din listă la 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 a 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 începe prin localizarea elementului din mijloc al matricei sortate de date
• După aceea, valoarea cheii este comparată cu elementul
• Dacă valoarea cheii este mai mică decât elementul din mijloc, atunci căutările analizează valorile superioare la elementul din mijloc pentru comparare și potrivire
• În cazul în care valoarea cheii este mai mare decât elementul din mijloc, atunci căutările analizează valorile inferioare la elementul din mijloc pentru comparare și potrivire

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 tabloului. Pentru a face acest lucru, luați valorile din stânga și din dreapta ale indexului și le împărțiți la 2. Rezultatul este 4.5, dar luăm valoarea de bază. Prin urmare, mijlocul este 4.
3. Algoritmul scade toate elementele de la mijloc (4) la limita inferioară, deoarece 59 este mai mare decât 24, iar acum matricea rămâne doar cu 5 elemente.
4. Acum, 59 este mai mare decât 45 și mai mic decât 63. Mijlocul este 7. Prin urmare, valoarea indexului din dreapta devine mijlocul – 1, care este egal cu 6, iar valoarea indexului din stânga rămâne aceeași ca înainte, care este 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ă ne uităm la următorul exemplu pentru a înțelege funcționarea căutării binare

1. Aveți o serie de valori sortate de la 2 la 20 și trebuie să găsiți 18.
2. Media limitelor inferioare și superioare este (l + r) / 2 = 4. Valoarea căutată este mai mare decât mijlocul care este 4.
3. Valorile matricei mai mici decât mijlocul 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 căutarea binară o alegere mai bună pentru a fi utilizată ca algoritm de căutare:

• Căutarea binară funcționează eficient pe datele sortate, indiferent de dimensiunea datelor
• Î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ă realizează comparații ale datelor sortate pe baza unui principiu de ordonare decât folosind comparații de egalitate, care sunt mai lente și în mare parte inexacte.
• După fiecare ciclu de căutare, algoritmul împarte dimensiunea matricei în jumătate, astfel încât în ​​următoarea iterație va funcționa numai în jumătatea rămasă a matricei

Aflați următorul nostru tutorial despre Căutare liniară: Python, C++ Exemplu

Rezumat

• Căutarea este un utilitar care permite utilizatorului să caute documente, fișiere și alte tipuri de date. 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 articole.
• Căutarea binară este cunoscută în mod obișnuit ca căutare pe jumătate de interval sau căutare logaritmică
• Funcționează prin împărțirea matricei în jumătate la fiecare iterație aflată sub elementul necesar.
• algoritm binar ia mijlocul matricei prin împărțirea sumei valorilor indexului din stânga și din dreapta la 2. Acum, algoritmul scade fie limita inferioară, fie limita superioară a elementelor din mijlocul matricei, în funcție de elementul care trebuie găsit.
• Algoritmul 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ă realizează comparații ale datelor sortate pe baza unui principiu de ordonare decât folosind comparații de egalitate care sunt lente și inexacte.
• O căutare binară nu este potrivită pentru date nesortate.