Puolitushaku

Wikipedia

Puolitushaku 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 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 muistivaatimus 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).