Binäärihaku on algoritmi, jolla voi löytää tietyn alkion n alkion järjestetystä taulukosta ajassa O(\log n). Tutustumme seuraavaksi binäärihaun toteuttamiseen sekä sen soveltamiseen algoritmiikassa.

Haun toteutus

Mukava tapa toteuttaa binäärihaku on aloittaa taulukon alusta ja kulkea sitä eteenpäin hyppäyksin. Hypyn pituus on ensin n, sitten n/2, sitten n/4, jne., kunnes lopuksi pituus on 1. Jokaisen pituuden kohdalla hypitään eteenpäin, kunnes seuraava hyppy veisi taulukon ulkopuolelle tai alkioon, joka on liian suuri.

Seuraava esimerkki etsii alkion x sijainnin järjestetyssä taulukossa t, jossa on n alkiota:

int k = 0;
for (int b = n; b >= 1; b /= 2) {
    while (k+b < n && t[k+b] <= x) k += b;
}
if (t[k] == x) // alkio löytyi

Muuttuja k ilmaisee kohdan taulukossa, ja se on aluksi 0. Muuttuja b määrittää hypyn pituuden. Jos taulukossa on alkio x, sen kohta on lopuksi muuttujassa k.

Algoritmi vie aikaa O(\log n), koska hypyn pituuksia on yhteensä O(\log n) ja jokaisen pituuden kohdalla while-silmukkaa suoritetaan enintään kaksi kierrosta.

Toistuvat alkiot

Äskeisessä binäärihaun toteutuksessa on etuna, että sitä on helppoa muokata eri tilanteisiin sopivaksi. Esimerkiksi seuraava koodi laskee, montako kertaa järjestetyssä taulukossa esiintyy alkio x:

int k1 = -1, k2 = -1;
for (int b = n; b >= 1; b /= 2) {
    while (k1+b < n && t[k1+b] < x) k1 += b;
    while (k2+b < n && t[k2+b] <= x) k2 += b;
}
c = k2-k1; // toistuvien alkioiden määrä

Tässä ideana on, että muuttujaan k_1 etsitään viimeinen kohta, jossa taulukon alkio on alle x, ja muuttujaan k_2 etsitään viimeinen kohta, jossa taulukon alkio on enintään x. Niinpä c=k_2-k_1 on alkion x toistokertojen määrä taulukossa.

Muutoskohdan etsiminen

Binäärihaun pääasiallinen käyttötarkoitus algoritmiikassa ei ole alkioiden etsiminen taulukosta vaan funktion muutoskohdan etsiminen.

Oletetaan, että meillä on funktio f, jolle pätee f(k)=0, kun k < m, ja f(k)=1, kun k \ge m. Binäärihaun avulla löydämme tehokkaasti muutoskohdan m näin:

int k = -1;
for (int b = N; b >= 1; b /= 2) {
    while (f(k+b) == 0) k += b;
}
int m = k+1;

Tässä N on sopiva yläraja, jossa varmasti f(N)=1, ja haku etsii viimeisen kohdan k, jolle pätee f(k)=0. Niinpä haun päätteeksi m=k+1. Haku vie aikaa O(\log N).

Esimerkki: Tehdas

Tarkastellaan tehtävää (tämän viikon tehtävä 1), jossa tehtaassa on n konetta, jotka on numeroitu 1,2,\dots,n. Koneella i vie k_i minuuttia aikaa valmistaa yksi tuote. Mikä on pienin aika, jossa voimme valmistaa t tuotetta?

Hyödyllinen havainto on, että jos aikaa on a minuuttia, voimme valmistaa koneella i yhteensä \lfloor a/k_i \rfloor tuotetta. Vastaavasti käyttämällä kaikkia koneita voimme valmistaa a minuutissa \sum_{i=1}^n \lfloor a/k_i \rfloor tuotetta.

Voimme ratkaista tehtävän binäärihaun avulla muotoilemalla funktion f niin, että f(a)=0, jos \sum_{i=1}^n \lfloor a/k_i \rfloor < t, ja muuten f(a)=1. Nyt funktion f muutoskohta m kertoo, mikä on pienin määrä aikaa, jossa voimme valmistaa t tuotetta.

Jotta voimme käyttää binäärihakua, meidän tulee valita jotenkin parametri N. Mahdollinen valinta on N=k_1 t. Tämä tarkoittaa, että valmistamme kaikki tuotteet koneen 1 avulla. Tämä ei selkeästi ole yleensä hyvä tapa, koska muita koneita ei käytetä lainkaan, mutta saamme tästä ylärajan vastaukselle.

Tuloksena oleva algoritmi vie aikaa O(n \log N), koska binäärihaussa on O(\log N) askelta ja jokaisen suorittaminen vie aikaa O(n).