Sisällysluettelo:
Määritelmä - Mitä binaarihaku tarkoittaa?
Binaarista hakualgoritmia käytetään lajiteltuun taulukkoon sisältyvän tietyn arvon sijainnin löytämiseen. Jakamisen ja valloittamisen periaatteen mukaisesti tämä hakualgoritmi voi olla melko nopea, mutta huomautus on, että tietojen on oltava lajiteltuina. Se toimii aloittamalla haku ryhmän keskeltä ja työskentelemällä alaspäin sekvenssin ensimmäisestä ala- tai yläosasta. Jos mediaaniarvo on alempi kuin tavoitearvo, se tarkoittaa, että haun täytyy mennä korkeammalle, jos ei, niin sen on katsottava taulukon laskevaa osaa.
Binaarinen haku tunnetaan myös nimellä puolivälin haku tai logaritminen haku.
Techopedia selittää binaarisen haun
Binaarinen haku on nopea ja tehokas tapa löytää tietty kohdearvo tilattujen tuotteiden joukosta. Aloittamalla lajitellun luettelon keskeltä, se voi tehokkaasti leikata hakutilan puoleen määrittämällä, nouseeko vai lasketaanko luettelo mediaaniarvon perusteella tavoitearvoon nähden.
Esimerkiksi tavoitearvolla 8 ja hakualueella 1-11:
- Mediaani / keskiarvo löytyy ja osoitin asetetaan siihen, mikä tässä tapauksessa on 6.
- Tavoitetta 8 verrataan kuuteen. Koska 6 on alle 8, tavoitteen on oltava ylemmässä puoliskossa.
- Osoitin siirretään seuraavaan arvoon (7) ja verrataan kohteeseen. Se on pienempi, joten osoitin siirtyy seuraavaan korkeampaan arvoon.
- Osoitin on nyt 8: lla. Verrattuna tähän tavoitteeseen, se on tarkka ottelu, joten tavoite on löydetty.
Binaarista hakua käytettäessä kohdetta oli verrattava vain kolmeen arvoon. Verrattuna lineaarisen haun tekemiseen, se olisi alkanut aivan ensimmäisestä arvosta ja siirtynyt ylöspäin, joutunut vertaamaan tavoitetta kahdeksaan arvoon. Binaarinen haku on mahdollista vain tilatulla tietosarjalla; jos tiedot on järjestetty satunnaisesti, niin lineaarinen haku tuottaa tuloksia koko ajan, kun taas binaarinen haku todennäköisesti olisi juuttunut ääretön silmukka.
