Binäärihakualgoritmi, jossa on EXAMPLE

Ennen kuin opimme binaarihaun, opimme:

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 lajiteltujen kohteiden luettelosta. Sen toimintaperiaate on jakaa listan tiedot puoleen, kunnes haluttu arvo löytyy ja näytetään käyttäjälle hakutuloksissa. Binäärihaku tunnetaan yleisesti nimellä a puolivälin haku tai logaritminen haku.

Kuinka binäärihaku toimii?

Binäärihaku toimii seuraavalla tavalla:

• Hakuprosessi alkaa etsimällä lajitellun tietojoukon keskimmäinen elementti
• Tämän jälkeen avaimen arvoa verrataan elementtiin
• Jos avainarvo on pienempi kuin keskielementti, haku analysoi ylemmän arvot keskielementtiin vertailua ja täsmäämistä varten.
• Jos avainarvo on suurempi kuin keskielementti, haku analysoi alemmat arvot keskielementtiin vertailua ja täsmäämistä varten

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 keskikohta. Tätä varten otat indeksin vasemman ja oikean puolen arvot ja jaat ne kahdella. Tulos on 2, mutta otamme pohjaarvon. Keskimmäinen on siis 4.5.
3. Algoritmi pudottaa kaikki elementit keskimmäisestä (4) alimmalle rajalle, koska 59 on suurempi kuin 24, ja nyt taulukkoon jää vain 5 elementtiä.
4. Nyt 59 on suurempi kuin 45 ja pienempi kuin 63. Keskimmäinen on 7. Siten oikeanpuoleisesta indeksistä tulee keskiarvo – 1, mikä on 6, ja vasemmanpuoleinen indeksin arvo 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ä ymmärtääksemme binäärihaun toiminnan

1. Sinulla on joukko lajiteltuja arvoja, jotka vaihtelevat välillä 2–20, ja sinun on löydettävä 18.
2. Ala- ja ylärajan keskiarvo on (l + r) / 2 = 4. Haettava arvo on suurempi kuin keskiarvo, joka on 4.
3. Keskiarvoa pienemmät taulukon arvot jätetään pois hausta ja keskiarvoa 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 valinnan käytettäväksi hakualgoritmina:

• Binäärihaku toimii tehokkaasti lajitetulla tiedolla datan 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 vertailut järjestysperiaatteella kuin tasavertailut, jotka ovat hitaampia ja enimmäkseen epätarkkoja.
• Jokaisen hakukierroksen jälkeen algoritmi jakaa taulukon koon puoleen, joten seuraavassa iteraatiossa se toimii vain taulukon loppupuolella

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

Yhteenveto

• Haku on apuohjelma, jonka avulla käyttäjä voi etsiä asiakirjoja, tiedostoja ja muun tyyppisiä tietoja. Binäärihaku on edistynyt hakualgoritmi, joka etsii ja hakee tietoja lajiteltujen kohteiden luettelosta.
• Binäärihaku tunnetaan yleisesti puolivälihakuna tai logaritmisena hakuna
• Se toimii jakamalla taulukon puoliksi jokaisessa iteraatiossa vaaditun elementin alla.
• - binäärialgoritmi ottaa taulukon keskikohdan jakamalla vasemman ja oikeanpuoleisimman indeksiarvojen summan 2:lla. Nyt algoritmi pudottaa joko elementtien ala- tai ylärajan taulukon keskeltä riippuen löydettävästä elementistä.
• Algoritmi hakee satunnaisesti tietoja löytääkseen tarvittavan elementin. Tämä tekee hakujaksoista lyhyempiä ja tarkempia.
• Binaarihaku vertailee lajiteltua dataa järjestysperiaatteella kuin käyttämällä hitaita ja epätarkkoja tasa-arvovertailuja.
• Binäärihaku ei sovellu lajittelemattomille tiedoille.