Ennen kuin opimme binaarihakua, opitaan:
Mikä on haku?
Haku on apuohjelma, jonka avulla käyttäjä voi löytää asiakirjoja, tiedostoja, mediaa tai muuta tietokannan sisällä olevaa dataa. Haku toimii yksinkertaisella periaatteella, jonka mukaan kriteerit sovitetaan yhteen tietueiden kanssa ja näytetään käyttäjälle. Tällä tavoin perushakutoiminto toimii.
Mikä on binaarihaku?
Binaarihaku on edistynyt hakualgoritmityyppi, joka etsii ja hakee tietoja lajiteltujen luetteloiden joukosta. Sen keskeisenä toimintaperiaatteena on jakaa tiedot luettelossa puoleen, kunnes vaadittu arvo löytyy ja näytetään käyttäjälle hakutuloksissa. Binaarihaku tunnetaan yleisesti puolivälin hauna tai logaritmisena hauna .
Tässä algoritmioppaassa opit:
- Mikä on haku?
- Mikä on binaarihaku?
- Kuinka binaarihaku toimii?
- Esimerkki binäärihausta
- Miksi tarvitsemme binaarihakua?
Kuinka binaarihaku toimii?
Binaarihaku toimii seuraavalla tavalla:
- Hakuprosessi aloitetaan paikantamalla lajiteltujen tietoryhmien keskiosa
- Sen jälkeen avainarvoa verrataan elementtiin
- Jos avainarvo on pienempi kuin keskielementti, haut analysoi ylemmät arvot keskielementtiin vertailua ja sovittamista varten
- Jos avainarvo on suurempi kuin keskielementti, haut analysoi keskiarvon alemmat arvot vertailua ja sovittamista varten
Esimerkki binäärihausta
Tarkastellaan sanakirjan esimerkkiä. Jos haluat löytää tietyn sanan, kukaan ei käy läpi jokaista sanaa peräkkäin, vaan etsii satunnaisesti lähimmät sanat etsimään tarvittavaa sanaa.
Yllä oleva kuva kuvaa seuraavaa:
- Sinulla on 10-numeroinen taulukko, ja elementti 59 on löydettävä.
- Kaikki elementit on merkitty indeksillä 0 - 9. Nyt lasketaan ryhmän keskiosa. Voit tehdä tämän ottamalla indeksin vasemman ja oikeanpuoleisimman arvon ja jakamalla ne arvolla 2. Tulos on 4,5, mutta me otamme lattia-arvon. Siksi keskimmäinen on 4.
- Algoritmi pudottaa kaikki elementit keskimmäisestä (4) alimpaan rajaan, koska 59 on suurempi kuin 24, ja nyt taulukossa on vain 5 elementtiä.
- Nyt 59 on suurempi kuin 45 ja alle 63. Keskimmäinen on 7. Siksi oikeasta indeksiarvosta tulee keskimmäinen - 1, joka on 6, ja vasen indeksiarvo pysyy samana kuin aiemmin, joka on 5.
- Tässä vaiheessa tiedät, että 59 tulee 45: n jälkeen. Siksi vasemmasta indeksistä, joka on 5, tulee myös puolivälissä.
- Nämä iteraatiot jatkuvat, kunnes matriisi on supistettu vain yhdeksi elementiksi tai löydettävä kohde muuttuu ryhmän keskiosaksi.
Esimerkki 2
Katsotaanpa seuraavaa esimerkkiä ymmärtääksemme binäärihaun toimivan
- Sinulla on joukko lajiteltuja arvoja, jotka vaihtelevat välillä 2-20, ja sinun on löydettävä 18.
- Ala- ja ylärajan keskiarvo on (l + r) / 2 = 4. Haettava arvo on suurempi kuin keskiarvo, joka on 4.
- Keskiarvoa pienemmät taulukon arvot pudotetaan hausta ja keskiarvoa 4 suuremmat arvot haetaan.
- Tämä on toistuva jakamisprosessi, kunnes todellinen etsittävä kohde löytyy.
Miksi tarvitsemme binaarihakua?
Seuraavat syyt tekevät binäärihausta paremman valinnan käytettäväksi hakualgoritmina:
- Binaarihaku toimii tehokkaasti lajitelluilla tiedoilla tietojen koosta riippumatta
- Sen sijaan, että suoritettaisiin haku käymällä läpi tiedot järjestyksessä, binaarialgoritmi käyttää satunnaisesti tietoja löytääkseen vaaditun elementin. Tämä tekee hakujaksoista lyhyempiä ja tarkempia.
- Binaarihaku tekee lajiteltujen tietojen vertailut järjestysperiaatteen perusteella kuin tasa-arvon vertailut, jotka ovat hitaampia ja enimmäkseen epätarkkoja.
- Jokaisen hakusyklin jälkeen algoritmi jakaa matriisin koon puoliksi, joten seuraavalla iteraatiolla se toimii vain taulukon jäljellä olevassa puoliskossa
Yhteenveto
- Haku on apuohjelma, jonka avulla käyttäjä voi etsiä asiakirjoja, tiedostoja ja muun tyyppisiä tietoja. Binaarihaku on edistynyt hakualgoritmityyppi, joka etsii ja hakee tietoja lajiteltujen luetteloiden joukosta.
- Binaarihaku tunnetaan yleisesti puolivälin hauna tai logaritmisena hauna
- Se toimii jakamalla matriisi puoliksi jokaisella iteroinnilla vaaditun elementin alapuolella.
- Binaarialgoritmi vie matriisin keskikohdan jakamalla vasemman ja oikeanpuoleisimman indeksiarvojen summan 2: lla. Nyt algoritmi pudottaa joko elementtien ala- tai ylärajan matriisin keskiosasta löydettävän elementin mukaan .
- Algoritmi käyttää tietoja satunnaisesti löytääkseen vaaditun elementin. Tämä tekee hakujaksoista lyhyempiä ja tarkempia.
- Binaarihaku tekee lajiteltujen tietojen vertailut järjestysperiaatteen perusteella kuin hitaiden ja epätarkkojen tasa-arvon vertailujen käyttö.
- Binaarihaku ei sovi lajittelemattomille tiedoille.