binäärihausta

Binäärihaku, tunnettu myös nimellä puolitushaku tai puolitusetsintä, on tehokas algoritmi järjestettyjen taulukoiden tai listojen tiettyjen alkioiden etsimiseen. Sen perusidea on jakaa hakualue jatkuvasti kahtia ja eliminoida aina se osa, jossa etsittävää alkiota ei voi olla.

Algoritmi alkaa tarkastelemalla järjestetyn taulukon keskimmäistä alkiota. Jos tämä alkio on etsittävä arvo, haku päättyy. Jos etsittävä arvo on pienempi kuin keskimmäinen alkio, haku jatkuu taulukon vasemmassa puoliskossa. Jos etsittävä arvo on suurempi, haku jatkuu oikeassa puoliskossa. Tätä prosessia toistetaan, kunnes alkio löytyy tai hakualue tyhjenee.

Binäärihaun tehokkuus perustuu sen logaritmiseen aikakompleksisuuteen, joka on O(log n), missä n on taulukon koko. Tämä tarkoittaa, että hakuajan kasvuvauhti on erittäin hidas verrattuna taulukon kokoon, mikä tekee siitä huomattavasti nopeamman kuin lineaarisessa haussa (O(n)) suurilla datamäärillä. Algoritmin käyttöönotto edellyttää, että etsittävä data on valmiiksi järjestetty jossakin ennalta määritellyssä järjestyksessä. Järjestämättömässä taulukossa binäärihakua ei voi käyttää.