Înainte de a învăța căutarea binară, să învățăm:
Ce este Căutarea?
Căutarea este un utilitar care permite utilizatorului său să găsească documente, fișiere, suporturi media sau orice alt tip de date păstrate în interiorul unei baze de date. Căutarea funcționează pe principiul simplu al potrivirii criteriilor cu înregistrările și afișarea acestuia către utilizator. În acest fel funcționează cea mai de bază funcție de căutare.
Ce este Binary Search?
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 principal de lucru 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 o căutare pe jumătate de interval sau o căutare logaritmică .
În acest tutorial algoritm, veți învăța:
- Ce este Căutarea?
- Ce este Binary Search?
- Cum funcționează căutarea binară?
- Exemplu Căutare binară
- De ce avem nevoie de căutare binară?
Cum funcționează căutarea binară?
Căutarea binară funcționează în modul următor:
- Procesul de căutare se inițiază prin localizarea elementului de mijloc al matricei sortate de date
- După aceea, valoarea cheie este comparată cu elementul
- Dacă valoarea cheii este mai mică decât elementul din mijloc, atunci căutările analizează valorile superioare ale elementului din mijloc pentru comparație și potrivire
- În cazul în care valoarea cheii este mai mare decât elementul de mijloc, atunci căutările analizează valorile inferioare ale elementului de mijloc pentru comparație și potrivire
Exemplu Căutare binară
Să ne uităm la exemplul unui dicționar. Dacă trebuie să găsiți un anumit cuvânt, nimeni nu trece prin fiecare cuvânt în mod secvențial, dar localizează aleatoriu cele mai apropiate cuvinte pentru a căuta cuvântul cerut.
Imaginea de mai sus ilustrează următoarele:
- Aveți o matrice de 10 cifre, iar elementul 59 trebuie găsit.
- Toate elementele sunt marcate cu indexul de la 0 la 9. Acum se calculează mijlocul matricei. Pentru a face acest lucru, luați valorile din stânga și dreapta ale indexului și le împărțiți la 2. Rezultatul este 4,5, dar noi luăm valoarea minimă. Prin urmare, mijlocul este 4.
- 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.
- Acum, 59 este mai mare de 45 și mai puțin de 63. Centrul este 7. Prin urmare, valoarea indicelui drept devine mijloc - 1, care este egal cu 6, iar valoarea indicelui stâng rămâne aceeași ca înainte, care este 5.
- În acest moment, știți că 59 vine după 45. Prin urmare, indicele din stânga, care este 5, devine și mijloc.
- Aceste iterații continuă până când matricea este redusă la un singur element sau elementul de găsit devine mijlocul matricei.
Exemplul 2
Să ne uităm la următorul exemplu pentru a înțelege funcționarea căutării binare
- Aveți o serie de valori sortate cuprinse între 2 și 20 și trebuie să localizați 18.
- Media limitelor inferioare și superioare este (l + r) / 2 = 4. Valoarea căutată este mai mare decât mijlocul care este 4.
- Valorile matricei mai mici decât media sunt eliminate din căutare și valorile mai mari decât valoarea medie 4 sunt căutate.
- Acesta este un proces de împărțire recurent până când este găsit elementul efectiv de căutat.
De ce avem nevoie de căutare binară?
Următoarele motive fac căutarea binară o alegere mai bună pentru a fi folosit ca algoritm de căutare:
- Căutarea binară funcționează eficient pe date sortate, indiferent de mărimea datelor
- În loc să efectueze căutarea parcurgând datele într-o succesiune, algoritmul binar accesează aleatoriu datele pentru a găsi elementul cerut. 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 decât folosind comparații de egalitate, care sunt mai lente și mai ales inexacte.
- După fiecare ciclu de căutare, algoritmul împarte dimensiunea matricei în jumătate, prin urmare, în următoarea iterație va funcționa doar în jumătatea rămasă a matricei
rezumat
- Căutarea este un utilitar care permite utilizatorului său 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 o căutare pe jumătate de interval sau o căutare logaritmică
- Funcționează împărțind matricea în jumătate pe fiecare iterație sub elementul necesar găsit.
- Algoritmul binar ia mijlocul matricei împărțind suma valorilor indexului din stânga și cea din dreapta la 2. Acum, algoritmul scade fie marginea inferioară, fie cea superioară a elementelor din mijlocul matricei, în funcție de elementul de 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ă efectuează 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.