Puolitushaku

Puolitushaku eli binäärihaku () 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 , missä  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  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

Aiheesta muualla 

Algoritmit