Binaarne otsingu algoritm koos EXAMPLE'iga

Enne binaarotsingu õppimist vaatame, mis otsing on.

Mis on otsing?

Otsing on utiliit, mis võimaldab selle kasutajal leida andmebaasis olevaid dokumente, faile, meediume või mis tahes muud tüüpi andmeid. Otsing töötab lihtsal põhimõttel, et kriteeriumid sobitatakse kirjetega ja kuvatakse see kasutajale. Sel viisil töötab kõige elementaarsem otsingufunktsioon.

Mis on binaarne otsing?

Binaarotsing on täiustatud otsingualgoritmi tüüp, mis leiab ja hangib andmeid sorteeritud üksuste loendist. Selle põhiline tööpõhimõte hõlmab loendis olevate andmete jagamist pooleks, kuni vajalik väärtus leitakse ja kuvatakse kasutajale otsingutulemustes. Binaarotsingut tuntakse tavaliselt kui poole intervalliga otsing või logaritmiline otsing.

Kuidas binaarne otsing töötab?

Binaarne otsing toimib järgmiselt:

• Otsinguprotsess algab sorteeritud andmemassiivi keskmise elemendi leidmisega.
• Pärast seda võrreldakse võtme väärtust elemendi väärtusega.
• Kui võtme väärtus on väiksem kui keskmine element, analüüsib otsing keskmise elemendi ülemisi väärtusi võrdlemiseks ja sobitamiseks.
• Kui võtme väärtus on suurem kui keskmise elemendi väärtus, analüüsib otsing keskmise elemendi suhtes madalamaid väärtusi võrdlemiseks ja sobitamiseks.

Binaarse otsingu algoritm (pseudokood)

Binaarotsingu saab kirjutada lühikese iteratiivse rutiinina. See hoiab kahte pointerit, madalat ja kõrget, ning kitsendab vahemikku, kuni sihtmärk leitakse või vahemik tühjeneb.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Rutiin tagastab edu korral sihtmärgi indeksi ja väärtuse puudumisel -1. Kuna vahemik pooleks iga läbimisega, töötab tsükkel maksimaalselt log₂(n) korda.

Binaarse otsingu näide

Vaatame sõnastiku näidet. Kui teil on vaja leida teatud sõna, ei vaata keegi iga sõna järjestikku läbi, vaid otsib vajaliku sõna otsimiseks juhuslikult lähimad sõnad.

Ülaltoodud pilt illustreerib järgmist:

1. Teil on 10-kohaline massiiv ja element 59 tuleb leida.
2. Kõik elemendid on tähistatud indeksiga 0 kuni 9. Nüüd arvutatakse massiivi keskmine väärtus. Selleks tuleb võtta indeksi vasak- ja parempoolseim väärtus ning jagada need 2-ga. Tulemuseks on 4.5, aga me võtame alumise väärtuse. Seega on keskmine väärtus 4.
3. Algoritm eemaldab kõik elemendid keskelt (4) alumisse piiri, kuna 59 on suurem kui 24 ja nüüd on massiivis ainult 5 elementi.
4. Nüüd on 59 suurem kui 45 ja väiksem kui 63. Keskmine on 7. Seega saab parempoolne indeksi väärtus keskmiseks − 1, mis võrdub 6-ga, ja vasakpoolne indeksi väärtus jääb samaks mis enne, mis on 5.
5. Siinkohal teate, et 59 tuleb pärast 45. Seega muutub ka vasakpoolne indeks, mis on 5, keskmiseks.
6. Need iteratsioonid jätkuvad seni, kuni massiiv väheneb ainult üheks elemendiks või leitav üksus muutub massiivi keskele.

Näiteks 2

Binaarotsingu toimimise mõistmiseks vaatame järgmist näidet.

1. Teil on sorteeritud väärtuste massiiv vahemikus 2 kuni 20 ja peate leidma 18.
2. Alumise ja ülemise piiri keskmine on (l + r) / 2 = 4. Otsitav väärtus on suurem kui keskmine väärtus, mis on 4.
3. Massiivi väärtused, mis on väiksemad kui keskmine väärtus, jäetakse otsingust välja ja otsitakse väärtusi, mis on suuremad kui keskmine väärtus 4.
4. See on korduv jagamisprotsess, kuni tegelik otsitav üksus leitakse.

Miks me vajame binaarset otsingut?

Järgmised põhjused muudavad binaarotsingu otsingualgoritmina paremaks valikuks:

• Binaarotsing töötab sorteeritud andmete puhul tõhusalt, olenemata andmete suurusest.
• Selle asemel, et otsida andmeid järjestikku läbides, pääseb binaaralgoritm vajaliku elemendi leidmiseks andmetele juhuslikult juurde. See muudab otsingutsüklid lühemaks ja täpsemaks.
• Binaarotsing võrdleb sorteeritud andmeid järjestamispõhimõtte alusel, mitte võrdusvõrdluste abil, mis on aeglasemad ja enamasti ebatäpsed.
• Pärast iga otsingutsüklit jagab algoritm massiivi suuruse pooleks; seega järgmises iteratsioonis töötab see ainult massiivi ülejäänud poolega.

Tutvu meie järgmise õpetusega Lineaarne otsing: Python, C++ Näide.

Binaarne otsing vs lineaarne otsing

Binaarotsing ja lineaarotsing on kaks kõige levinumat viisi väärtuse leidmiseks kollektsioonist. Allolev tabel toob esile nende erinevused.

Lühidalt, binaarotsing on suurte sorteeritud andmete puhul palju kiirem, samas kui lineaarne otsing on lihtsam ja ainus võimalus, kui andmed pole sorteeritud.

KKK