Puolitushaku

Puolitushaku eli binäärihaku (Malline:K-en) on tietojenkäsittelytieteessä tehokas ja yleisesti käytetty hakualgoritmi tiedon etsimiseen järjestetystä taulukosta.

Puolitushaun ideana on etsiä etsittävää alkiota taulukon keskeltä, ja mikäli alkiota ei löytynyt, voidaan alkion etsimistä jatkaa alkuperäisen taulukon alku- tai loppupään puolivälistä riippuen siitä onko haettava arvo pienempi vai suurempi kuin taulukon keskellä oleva alkio. Koska jokainen hakuaskel puolittaa taulukon josta alkiota haetaan, on algoritmin asymptoottinen suoritusaika $O(\log n)$, missä $n$ on alkioiden lukumäärä. Voidaan osoittaa, että tätä asymptoottisesti nopeampaa vertailuihin perustuvaa algoritmia etsiä alkio taulukosta ei ole.

Seuraava puolitushaun pseudokoodi palauttaa indeksin, josta haettava alkio löytyy:

Puolitushaku(taulu, haettava, vasen, oikea)
    while vasen <= oikea
        keski = (vasen+oikea)/2
        if taulu[keski] == haettava
            return keski
        if haettava < taulu[keski]
            oikea = keski-1
        else 
            vasen = keski+1
    return null

Koska yllä oleva algoritmi ei käytä rekursiota, on tilavaativuus yllä olevassa toteutuksessa $O(1)$ eli algoritmi vaatii vain vakiomäärän muistia.

Käytännössä moni ohjelmoija tekee virheen kirjoittaessaan (vasen + oikea) / 2, sillä useimmissa ohjelmointikielissä kokonaislukuarvo vasen + oikea voi pyörähtää tällöin ympäri. Oikea ratkaisu on kirjoittaa esimerkiksi vasen + ((oikea – vasen) / 2).Malline:Kenen mukaan

Lähteet

• Malline:Kirjaviite