Puolitushaku

Puolitushaku eli binäärihaku (engl. binary search) 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).

Lähteet

• Grossman, David A. & Frieder, Ophir: Information retrieval: algorithms and heuristics. Second edition. Dordrecht: Springer, 2004. ISBN 1-4020-3003-7. (englanniksi)

Aiheesta muualla

• Kuvia tai muita tiedostoja aiheesta Puolitushaku Wikimedia Commonsissa