Cuprins:
Definiție - Ce înseamnă căutarea binară?
Un algoritm de căutare binară este utilizat pentru a găsi poziția unei valori specifice conținute într-un tablou sortat. Lucrând cu principiul de împărțire și de cucerire, acest algoritm de căutare poate fi destul de rapid, dar informația este că datele trebuie să fie într-o formă sortată. Funcționează începând căutarea în mijlocul tabloului și lucrând în jos în prima jumătate inferioară sau superioară a secvenței. Dacă valoarea mediană este mai mică decât valoarea țintă, aceasta înseamnă că căutarea trebuie să se ridice, dacă nu, atunci trebuie să se uite la porțiunea descendentă a tabloului.
O căutare binară este, de asemenea, cunoscută sub numele de căutare la jumătate de interval sau de căutare logaritmică.
Techopedia explică căutarea binară
O căutare binară este o metodă rapidă și eficientă de a găsi o valoare țintă specifică dintr-un set de articole comandate. Începând din mijlocul listei sortate, acesta poate reduce efectiv spațiul de căutare la jumătate, determinând dacă se ascunde sau coboară lista pe baza valorii mediane în comparație cu valoarea țintă.
De exemplu, cu o valoare țintă de 8 și un spațiu de căutare de la 1 la 11:
- Valoarea mediană / mijlocie este găsită și indicatorul este setat acolo, care în acest caz este 6.
- Tinta de 8 este comparată cu 6. Deoarece 6 este mai mic decât 8, ținta trebuie să fie în jumătatea superioară.
- Indicatorul este mutat la următoarea valoare (7) și comparat cu ținta. Este mai mic, de aceea indicatorul trece la următoarea valoare mai mare.
- Indicatorul este acum 8. Comparativ cu această țintă, este o potrivire exactă, prin urmare, ținta a fost găsită.
Folosind căutarea binară, ținta a trebuit să fie comparată doar cu trei valori. În comparație cu efectuarea unei căutări liniare, aceasta ar fi pornit de la prima valoare și s-ar fi avansat, fiind necesar să se compare ținta cu opt valori. O căutare binară este posibilă numai cu un set ordonat de date; dacă datele sunt aranjate la întâmplare, atunci o căutare liniară ar da rezultate tot timpul, în timp ce o căutare binară ar fi probabil blocată într-o buclă infinită.
