Binäärihakualgoritmi, jossa on EXAMPLE

Ennen kuin opettelemme binäärihakua, katsotaanpa, mitä haku on.

Mikä on haku?

Haku on apuohjelma, jonka avulla sen käyttäjä voi löytää asiakirjoja, tiedostoja, mediaa tai mitä tahansa muuta tietokannan sisällä olevaa tietoa. Haku toimii sillä yksinkertaisella periaatteella, että kriteerit täsmäytetään tietueiden kanssa ja näytetään käyttäjälle. Tällä tavalla yksinkertaisin hakutoiminto toimii.

Mikä on binaarihaku?

Binäärihaku on edistynyt hakualgoritmi, joka etsii ja hakee tietoja lajitellusta luettelosta. Sen ydintoimintaperiaatteena on jakaa luettelon tiedot kahtia, kunnes haluttu arvo löytyy ja näytetään käyttäjälle hakutuloksissa. Binäärihaku tunnetaan yleisesti nimellä puolivälin haku tai logaritminen haku.

Kuinka binäärihaku toimii?

Binäärihaku toimii seuraavalla tavalla:

• Hakuprosessi alkaa paikantamalla lajitellun datataulukon keskimmäinen elementti.
• Sen jälkeen avaimen arvoa verrataan elementin arvoon.
• Jos avaimen arvo on pienempi kuin keskimmäinen elementti, haku analysoi ylemmät arvot keskimmäiseen elementtiin verrattuna vertailua ja vastaavuuksien löytämistä varten.
• Jos avaimen arvo on suurempi kuin keskimmäisen elementin arvo, haku analysoi keskimmäisen elementin alemmat arvot vertailua ja vastaavuutta varten.

Binäärihakualgoritmi (pseudokoodi)

Binäärihaku voidaan kirjoittaa lyhyenä, iteratiivisena rutiinina. Se pitää kaksi osoitinta, matalan ja korkean, ja kaventaa aluetta, kunnes kohde löytyy tai alue tyhjenee.

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

Rutiini palauttaa kohteen indeksin onnistuessaan ja arvon -1, jos arvoa ei ole. Koska alue puolittuu jokaisella suorituskerralla, silmukka suoritetaan enintään log₂(n) kertaa.

Esimerkki binaarihausta

Katsotaanpa esimerkkiä sanakirjasta. Jos sinun on löydettävä tietty sana, kukaan ei käy läpi jokaista sanaa peräkkäin, vaan etsii satunnaisesti lähimmät sanat etsiäkseen vaadittua sanaa.

Yllä oleva kuva havainnollistaa seuraavaa:

1. Sinulla on 10 numeron taulukko, ja elementti 59 on löydettävä.
2. Kaikki alkiot on merkitty indeksillä 0–9. Nyt lasketaan taulukon keskimmäinen arvo. Tätä varten otetaan indeksin vasen ja oikea arvo ja jaetaan ne kahdella. Tulos on 4.5, mutta otamme pohjan arvon. Näin ollen keskimmäinen on 4.
3. Algoritmi pudottaa kaikki elementit keskeltä (4) alimpaan rajaan, koska 59 on suurempi kuin 24, ja nyt taulukossa on jäljellä vain 5 elementtiä.
4. Nyt 59 on suurempi kuin 45 ja pienempi kuin 63. Keskimmäinen on 7. Näin ollen oikeanpuoleinen indeksiarvo on keskimmäinen − 1, joka on yhtä kuin 6, ja vasemmanpuoleinen indeksiarvo pysyy samana kuin ennen eli 5.
5. Tässä vaiheessa tiedät, että 59 tulee 45:n jälkeen. Siten vasemmasta indeksistä, joka on 5, tulee myös keskiarvo.
6. Nämä iteraatiot jatkuvat, kunnes matriisi on pelkistetty vain yhteen elementtiin tai löydettävä kohde tulee taulukon keskikohtaan.

Esimerkki 2

Katsotaanpa seuraavaa esimerkkiä binäärihaun toiminnan ymmärtämiseksi.

1. Sinulla on joukko lajiteltuja arvoja, jotka vaihtelevat välillä 2–20, ja sinun on löydettävä 18.
2. Ala- ja ylärajojen keskiarvo on (l + r) / 2 = 4. Haettava arvo on suurempi kuin keskiarvo, joka on 4.
3. Keskimmäistä arvoa pienemmät taulukon arvot jätetään pois hausta ja keskimmäistä arvoa 4 suuremmat arvot haetaan.
4. Tämä on toistuva jakoprosessi, kunnes varsinainen haettava kohde löytyy.

Miksi tarvitsemme binaarihakua?

Seuraavat syyt tekevät binäärihausta paremman vaihtoehdon hakualgoritmina:

• Binäärihaku toimii tehokkaasti lajitellussa datassa koosta riippumatta.
• Sen sijaan, että binäärialgoritmi suorittaisi haun käymällä tiedot läpi järjestyksessä, binäärialgoritmi hakee tietoja satunnaisesti löytääkseen tarvittavan elementin. Tämä tekee hakujaksoista lyhyempiä ja tarkempia.
• Binäärihaku suorittaa lajiteltujen tietojen vertailuja järjestysperiaatteen perusteella pikemminkin kuin käyttämällä yhtäsuuruusvertailuja, jotka ovat hitaampia ja enimmäkseen epätarkkoja.
• Jokaisen hakukierroksen jälkeen algoritmi jakaa taulukon koon puoleen; näin ollen seuraavassa iteraatiossa se työskentelee vain taulukon jäljellä olevan puoliskon kanssa.

Opi seuraava opetusohjelmamme aiheesta Lineaarinen haku: Python, C++ esimerkki.

Binäärihaku vs. lineaarihaku

Binäärihaku ja lineaarihaku ovat kaksi yleisintä tapaa löytää arvo joukosta. Alla oleva taulukko havainnollistaa, miten ne eroavat toisistaan:

Lyhyesti sanottuna binäärihaku on paljon nopeampi suurissa lajitelluissa tiedoissa, kun taas lineaarinen haku on yksinkertaisempi ja ainoa vaihtoehto, kun tietoja ei ole lajiteltu.

UKK