Moni koodari on yrittänyt toteuttaa binäärihaun, mutta tuskin kukaan on onnistunut siinä. Tämän jutun luettuasi voit liittyä harvojen ja valittujen joukkoon.

Artikkeli on alun perin julkaistu Skrollin numerossa 2014.1.

Voit tilata lehden kätevästi täältä, niin voit lukea jutut kätevästi heti lehden saapuessa!

Teksti: Antti Laaksonen
Kuva: Mitol Berschewsky

Binäärihaku on ohjelmoinnin teorian tunnetuimpia algoritmeja. Sen avulla voi esimerkiksi tarkistaa tehokkaasti, esiintyykö annettu luku järjestetyssä taulukossa. Toisaalta binäärihaku on tullut tunnetuksi myös siitä, että algoritmin toteuttaminen virheettömästi on lähestulkoon mahdotonta. Näin asia onkin, jos algoritmin toteuttaa perinteisellä menetelmällä. Toteuttaminen muuttuu kuitenkin lastenleikiksi, kun valitaan toisenlainen lähestymistapa.

Binäärihaulla olisit jo perillä

Oletetaan, että taulukko T sisältää n lukua ja että tehtävänä on tarkistaa, esiintyykö luku k taulukossa. Yksinkertaisin algoritmi tähän tehtävään on lineaarihaku, joka käy läpi taulukon luvut yksi kerrallaan. C-sukuisella kielellä lineaarihaun voisi toteuttaa seuraavasti:

for (int i = 0; i < n; i++)

 if (T[i] == k)

  return true;

return false;

Tarkistusta ei voi tehdä lineaarihakua tehokkaammin, jos taulukon alkiot voivat olla sekaisin. Tällöin etsittävä alkio voi olla missä tahansa taulukon kohdassa, ja algoritmin täytyy pahimmassa tapauksessa käydä läpi kaikki alkiot. Tilanne kuitenkin muuttuu, jos taulukon sisältö on järjestetty. Tällöin binäärihaku on ylivertaisen tehokas algoritmi etsimiseen.

Perinteinen binäärihakuun liittyvä vertauskuva on nimen etsiminen puhelinluettelosta. Aluksi puhelinluettelo avataan keskeltä ja katsotaan, mikä nimi siinä kohdassa on. Nyt haun voi rajoittaa luettelon alkuosaan tai loppuosaan riippuen siitä, mikä nimi on luettelon keskellä. Hakualuetta puolitetaan tällä tavalla yhä uudestaan, kunnes alue on niin pieni, että nimi löytyy helposti. Idea on hauska, mutta ikävä kyllä binäärihaun koodaaminen bugittomasti on tämän pohjalta vaikeaa.

Helpompi lähestymistapa on ajatella binäärihakua lineaarihaun tehostuksena. Ideana on siirtyä taulukossa eteenpäin hyppäyksin. Ensin hypyn pituus on n/2 indeksiä, sitten n/4 indeksiä, sitten n/8 indeksiä jne. Haun alussa voidaan tehdä pitkiä loikkia, mutta vauhti hidastuu, kun tullaan lähemmäksi etsittävää lukua. Tuloksena on seuraava koodi:

int i = 0;

for (int b = n / 2; b >= 1; b /= 2)

 while (i + b < n && T[i + b] <= k)

  i += b;

return T[i] == k;

Muuttuja b määrittää, kuinka suuria hyppyjä haussa tehdään. Jokaisen hypyn pituuden kohdalla liikutaan niin monta hyppyä eteenpäin kuin mahdollista menemättä taulukon oikean reunan yli tai sellaiseen lukuun, joka on etsittävää lukua suurempi. Kuten aiemminkin, muuttuja i on taulukkoon osoittava indeksi. Haun päätteeksi i osoittaa kohtaan, jossa haettava luku esiintyy taulukossa, mikäli sellainen kohta on olemassa.

Matemaattisesti ilmaistuna lineaarihaku tarkistaa pahimmillaan n taulukon kohtaa, kun taas binäärihaku tarkistaa vain noin log₂ n kohtaa. Binäärihaun askelten logaritminen määrä johtuu siitä, että hypyn pituus puolittuu jokaisessa vaiheessa. Lisäksi tiettyä hypyn pituutta vastaavia askelia tehdään käytännössä korkeintaan kaksi. Ero n:n ja log₂ n:n tarkistuksen välillä on todella merkittävä, kun n on suuri luku. Esimerkiksi jos n on miljoona, log₂ n on vain noin 20.

Vaikeampaa kuin arvaisi

Binäärihaun toteuttaminen on yllättävän vaikeaa. Jon Bentley antaa tästä esimerkin kirjassaan Programming Pearls (1986). Bentley suoritti useita kertoja kokeen, jossa ammattiohjelmoijat saivat tehtäväkseen toteuttaa binäärihaun puhelinluetteloesimerkin perusteella. Muutaman tunnin kuluttua lähes kaikki ilmoittivat saaneensa algoritmin valmiiksi, mutta tarkemman tutkimuksen jälkeen osoittautui, että vain noin 10 % toteutuksista oli toimivia. 20 vuotta Bentleyn kirjan julkaisun jälkeen paljastui, että myös kirjassa esitetyssä binäärihaun toteutuksessa on bugi!

Mitä sillä tekee?

Osaamme nyt koodata toimivan binäärihaun, mutta mihin sitä voisi käyttää? Yllättävää kyllä, binäärihakua käytetään nykyään harvoin järjestetystä taulukosta hakemiseen, sillä useimmissa ohjelmointikielissä on valmiina paljon monipuolisempia tietorakenteita. Esimerkiksi C++:ssa voi käyttää std::set-luokkaa, joka tukee tehokkaan haun lisäksi myös tehokasta alkion lisäämistä ja poistamista.

Binäärihaulla on kuitenkin muitakin sovelluksia. Tutkitaan vaikkapa tieverkkoa, jossa on kaupunkeja sekä kahden kaupungin välisiä teitä. Jokaisesta tienpätkästä tiedetään, paljonko polttoainetta sillä ajaminen kuluttaa. Autot voivat tankata kaupungeissa mutta eivät tieosuuksilla.

Minkä kokoinen polttoainesäiliö autossa täytyy vähintään olla, jotta sillä voi ajaa mistä vain kaupungista mihin tahansa toiseen kaupunkiin?

Kuvassa 1 on esimerkki tieverkosta. Jokainen kuvan ympyrä vastaa kaupunkia, jotka on merkitty tunnuksin A, B, C ja D. Kaupunkien väliset tiet on merkitty viivoin. Esimerkiksi kaupungista B pääsee kaupunkiin C kuluttamalla kolme litraa polttoainetta.

Tehtävän ratkaisussa kannattaa ensin miettiä yksinkertaisempaa ongelmaa: jos polttoainesäiliön koko on x litraa, onko mahdollista ajaa minkä tahansa kahden kaupungin välillä?

Ongelma ratkeaa näin: Valitaan mikä tahansa kaupunki lähtökaupungiksi ja merkitään se ruksilla. Sitten merkitään kaikki kaupungit, joihin lähtökaupungista pääsee x litralla polttoainetta. Tämän jälkeen merkitään vastaavasti kaikki kaupungit, joihin pääsee viimeksi merkityistä kaupungeista. Samaa toistetaan niin kauan kuin uusia kaupunkeja tulee mukaan. Jos lopussa kaikki kaupungit on merkitty, x litraa riittää minkä tahansa kahden kaupungin välillä ajamiseen.

Annetaan nimi riittaa(x) funktiolle, joka palauttaa true, jos x litran säiliö riittää kaikkien kaupunkien välillä, ja muuten false. Jos tehtävän ratkaisu on r litraa, riittaa(x) palauttaa false aina, kun x on r–1 tai vähemmän, ja true aina, kun x on r tai enemmän.

Funktion arvoissa on siis yksi muutoskohta, jonka vasemmalla puolella jokainen arvo on false ja oikealla puolella jokainen arvo on true. Lisäksi tiedämme, että kaupungista toiseen pääsee ainakin silloin, kun polttoainesäiliö riittää kaikille tieosuuksille. Näiden ominaisuuksien ansiosta tehtävän voi ratkaista tehokkaasti binäärihaulla funktiota riittaa(x) käyttäen:

int v = 0;

for (int b = s / 2; b >= 1; b /= 2)

 while (!riittaa(v + b))

  v += b;

return v + 1;

Muuttujassa s on tieverkon vaativimman tieosuuden polttoainekulutus. Tämä arvo on luonteva valinta binäärihaun ylärajaksi. Koodi laskee muuttujaan v suurimman polttoainemäärän, joka ei riitä minkä tahansa kahden kaupungin välillä ajamiseen. Tehtävän vastaus on siten yhden suurempi kuin tämä arvo. Binäärihaun ansiosta funktiota riittaa(x) täytyy kutsua vain noin log₂ s kertaa.

Vastaavaa menetelmää voi soveltaa aina, kun etsitään lukua ja osataan tunnistaa, onko jokin annettu luku pienempi vai suurempi kuin etsitty luku. Binäärihaun ansiosta ei tarvitse käydä läpi kaikkia mahdollisia arvoja vaan logaritminen määrä riittää. Algoritmista tulee siis tehokas.

Artikkeli on alun perin julkaistu Skrollin numerossa 2014.1.

Voit tilata lehden kätevästi täältä, niin voit lukea jutut kätevästi heti lehden saapuessa!