Enne binaarotsingu õppimist õppime:
Mis on otsing?
Otsing on utiliit, mis võimaldab kasutajal leida andmebaasis olevaid dokumente, faile, meediume või mis tahes muud tüüpi andmeid. Otsing töötab lihtsal põhimõttel, et kriteeriumid kirjetega sobitada ja kasutajale kuvada. Sel viisil töötab kõige elementaarsem otsingufunktsioon.
Mis on binaarotsing?
Binaarotsing on täpsem otsingualgoritmi tüüp, mis otsib ja toob andmeid üksuste järjestatud loendist. Selle peamine tööpõhimõte seisneb selles, et loendis olevad andmed jagatakse pooleks, kuni vajalik väärtus on leitud ja kasutajale otsingutulemites kuvatud. Binaarotsingut tuntakse tavaliselt kui poolintervalli või logaritmilist otsingut .
Selles algoritmiõpetuses saate teada:
- Mis on otsing?
- Mis on binaarotsing?
- Kuidas binaarotsing töötab?
- Binaarotsingu näide
- Miks me vajame binaarset otsingut?
Kuidas binaarotsing töötab?
Binaarotsing töötab järgmiselt:
- Otsimisprotsess algatatakse sorteeritud andmemassiivi keskmise elemendi leidmisega
- Pärast seda võrreldakse põhiväärtust elemendiga
- Kui võtme väärtus on väiksem kui keskmine element, analüüsib otsing võrdlemiseks keskmise elemendi ülemisi väärtusi
- Kui võtmeväärtus on suurem kui keskmine element, analüüsib otsing keskmise elemendi madalamaid väärtusi võrdlemiseks ja sobitamiseks
Binaarotsingu näide
Vaatame sõnaraamatu näidet. Kui peate leidma kindla sõna, ei käi keegi iga sõna järjest läbi, vaid otsib juhuslikult lähimad sõnad vajaliku sõna otsimiseks.
Ülaltoodud pilt illustreerib järgmist:
- Teil on 10-kohaline massiiv ja element 59 tuleb leida.
- Kõik elemendid on tähistatud indeksiga 0 - 9. Nüüd arvutatakse massiivi keskosa. Selleks võtate indeksi vasakpoolse ja parempoolse väärtuse ning jagate need 2-ga. Tulemuseks on 4,5, kuid me võtame põranda väärtuse. Seega on keskmine 4.
- Algoritm langetab kõik elemendid keskelt (4) madalaima piirini, kuna 59 on suurem kui 24, ja nüüd jääb massiivi ainult 5 elementi.
- Nüüd on 59 suurem kui 45 ja väiksem kui 63. Keskmine on 7. Seega muutub parempoolne indeksi väärtus keskeks - 1, mis võrdub 6-ga, ja vasakpoolne indeksi väärtus jääb samaks nagu varem, mis on 5.
- Siinkohal teate, et 59 järgneb 45-le. Seega saab vasakpoolne indeks, mis on 5, samuti keskmiseks.
- Neid iteratsioone jätkatakse seni, kuni massiiv on vähendatud ainult üheks elemendiks või leitav element saab massiivi keskpaigaks.
Näide 2
Vaatame järgmist näidet, et mõista kahendotsingu toimimist
- Teil on sorteeritud väärtuste massiiv vahemikus 2 kuni 20 ja peate leidma 18.
- Alumise ja ülemise piiri keskmine on (l + r) / 2 = 4. Otsitav väärtus on suurem kui keskosa, mis on 4.
- Massiiviväärtused, mis on väiksemad kui keskpaigad, jäetakse otsingust välja ja otsitakse väärtusi, mis on suuremad kui keskväärtus 4.
- See on korduv jagamisprotsess kuni tegeliku otsitava üksuse leidmiseni.
Miks me vajame binaarset otsingut?
Järgmised põhjused muudavad binaarotsingu paremaks otsingu algoritmina kasutamiseks:
- Binaarotsing töötab sorteeritud andmetel tõhusalt, olenemata andmete suurusest
- Selle asemel, et otsida andmeid järjestikku läbi käies, pääseb binaaralgoritm juhuslikult andmetele juurde, et leida vajalik element. See muudab otsingutsüklid lühemaks ja täpsemaks.
- Binaarotsing teostab järjestatud andmete võrdlemist järjestusprintsiibil, mitte võrdõiguslikkuse võrdluste abil, mis on aeglasemad ja enamasti ebatäpsed.
- Pärast igat otsingutsüklit jagab algoritm massiivi suuruse pooleks, seega järgmises iteratsioonis töötab see ainult massiivi ülejäänud pooles
Kokkuvõte
- Otsing on utiliit, mis võimaldab kasutajal otsida dokumente, faile ja muud tüüpi andmeid. Binaarotsing on täpsem otsingualgoritmi tüüp, mis otsib ja toob andmeid üksuste järjestatud loendist.
- Binaarotsingut tuntakse tavaliselt kui poolintervalli või logaritmilist otsingut
- See toimib jagades massiivi pooleks igal leitud iteratsiooni korral.
- Binaaralgoritm võtab massiivi keskosa, jagades vasakpoolse ja parempoolse indeksi väärtuste summa 2-ga. Nüüd langetab algoritm massiivi keskelt kas elementide alumise või ülemise piiri, sõltuvalt leitavast elemendist .
- Vajaliku elemendi leidmiseks pääseb algoritm juhuslikult andmetele ligi. See muudab otsingutsüklid lühemaks ja täpsemaks.
- Binaarotsinguga võrreldakse järjestatud andmeid järjestusprintsiibi alusel kui aeglase ja ebatäpse võrdõiguslikkuse võrdluse abil.
- Binaarotsing ei sobi sorteerimata andmete jaoks.