Preden se naučimo binarnega iskanja, se naučimo:
Kaj je iskanje?
Iskanje je pripomoček, ki uporabniku omogoča iskanje dokumentov, datotek, medijev ali katere koli druge vrste podatkov v bazi podatkov. Iskanje deluje po preprostem principu, da se merila ujemajo z zapisi in prikažejo uporabniku. Na ta način deluje najosnovnejša funkcija iskanja.
Kaj je binarno iskanje?
Binarno iskanje je napredna vrsta algoritma iskanja, ki najde in pridobi podatke iz razvrščenega seznama elementov. Njeno glavno načelo dela je delitev podatkov na seznamu na polovico, dokler se zahtevana vrednost ne najde in prikaže uporabniku v rezultatih iskanja. Binarno iskanje je splošno znano kot iskanje s pol intervala ali logaritemsko iskanje .
V tej vadnici algoritma boste izvedeli:
- Kaj je iskanje?
- Kaj je binarno iskanje?
- Kako deluje binarno iskanje?
- Primer binarnega iskanja
- Zakaj potrebujemo binarno iskanje?
Kako deluje binarno iskanje?
Binarno iskanje deluje na naslednji način:
- Postopek iskanja se začne tako, da poišče srednji element razvrščenega polja podatkov
- Po tem se ključna vrednost primerja z elementom
- Če je vrednost ključa manjša od srednjega elementa, potem iskanje analizira zgornje vrednosti do srednjega elementa za primerjavo in ujemanje
- Če je vrednost ključa večja od srednjega elementa, potem iskanje analizira spodnje vrednosti za srednji element za primerjavo in ujemanje
Primer binarnega iskanja
Oglejmo si primer slovarja. Če morate poiskati določeno besedo, nihče ne gre zaporedoma skozi vsako besedo, temveč naključno poišče najbližje besede, da bi poiskal zahtevano besedo.
Zgornja slika ponazarja naslednje:
- Imate polje 10 števk in treba je najti element 59.
- Vsi elementi so označeni z indeksom od 0 do 9. Zdaj se izračuna sredina matrike. Če želite to narediti, vzamete levo in desno vrednost indeksa in jih delite z 2. Rezultat je 4,5, mi pa vzamemo talno vrednost. Sredina je torej 4.
- Algoritem spusti vse elemente od sredine (4) na najnižjo mejo, ker je 59 več kot 24, zdaj pa je matriki ostalo samo 5 elementov.
- Zdaj je 59 več kot 45 in manj kot 63. Sredina je 7. Zato desna vrednost indeksa postane srednja - 1, kar je enako 6, vrednost levega indeksa pa ostane enaka kot prej, kar je 5.
- Na tej točki veste, da 59 pride po 45. Zato tudi levi indeks, ki je 5, postane srednji.
- Te ponovitve se nadaljujejo, dokler se matrika ne zmanjša na samo en element ali pa element, ki ga najdemo, postane sredina polja.
2. primer
Oglejmo si naslednji primer, da bi razumeli, kako deluje binarno iskanje
- Imate vrsto razvrščenih vrednosti od 2 do 20 in jih morate poiskati 18.
- Povprečje spodnje in zgornje meje je (l + r) / 2 = 4. Iskana vrednost je večja od sredine, ki je 4.
- Vrednosti polja, ki so manjše od srednje, se izpustijo iz iskanja, vrednosti, večje od srednje vrednosti 4, pa se poiščejo.
- To je ponavljajoč se postopek delitve, dokler ne najdemo dejanskega predmeta, ki ga želimo iskati.
Zakaj potrebujemo binarno iskanje?
Zaradi naslednjih razlogov je binarno iskanje boljša izbira za uporabo kot algoritem iskanja:
- Binarno iskanje učinkovito deluje na razvrščenih podatkih, ne glede na njihovo velikost
- Namesto da bi binarni algoritem izvedel iskanje po podatkih v zaporedju, naključno dostopa do podatkov in poišče zahtevani element. Tako so cikli iskanja krajši in natančnejši.
- Binarno iskanje izvaja primerjave razvrščenih podatkov na principu razvrščanja kot pa primerjave enakovrednosti, ki so počasnejše in večinoma netočne.
- Po vsakem ciklu iskanja algoritem deli velikost polja na polovico, zato bo v naslednji ponovitvi deloval le v preostali polovici polja
Povzetek
- Iskanje je pripomoček, ki uporabniku omogoča iskanje dokumentov, datotek in drugih vrst podatkov. Binarno iskanje je napredna vrsta algoritma iskanja, ki najde in pridobi podatke iz razvrščenega seznama elementov.
- Binarno iskanje je splošno znano kot iskanje s pol intervala ali logaritemsko iskanje
- Deluje tako, da matriko razdeli na polovico na vsaki ponovitvi pod zahtevanim elementom.
- Binarni algoritem zavzame sredino polja tako, da vsoto leve in skrajne desne vrednosti indeksa deli z 2. Algoritem spusti bodisi spodnjo bodisi zgornjo mejo elementov iz sredine polja, odvisno od elementa, ki ga najdemo .
- Algoritem naključno dostopa do podatkov in poišče zahtevani element. Tako so cikli iskanja krajši in natančnejši.
- Binarno iskanje izvaja primerjave razvrščenih podatkov na podlagi načela razvrščanja kot pa pri primerjavah enakosti, ki so počasne in netočne.
- Binarno iskanje ni primerno za nesortirane podatke.